Title:

A new sufficient condition for a digraph to be Hamiltonian−A proof of Manoussakis conjecture

Author:

Darbinyan Samvel Kh.

Type:

article

Uncontrolled Keywords:

digraph ; hamiltonian cycle ; strong digraph ; pancyclic digraph

Abstract:

In this paper, we confirm this conjecture. Moreover, we prove that if a digraph D satisfies the conditions of this conjecture and has a pair of non-adjacent vertices {x, y} such that d(x) + d(y)  2n − 4, then D contains cycles of all lengths 3, 4, . . . , n.

Publisher:

DMTCS

Date submitted:

2020-02-11

Date accepted:

2020-11-05

Date modified:

2020-07-21, 2020-11-05,

Date of publication:

2021-01-18

DOI:

10.23638/DMTCS-22-4-12

Language:

English

Journal or Publication Title:

Discrete Mathematics & Theoretical Computer Science

Volume:

22

Number:

4

URL:

Additional Information:

The author would like to thank the anonymous referees for thoroughly review and many helpful commentsand suggestions which improved substantially the rewriting of this paper. We also thank PhD P. Hakobyanfor formatting the manuscript of this paper.

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Year:

2021

References:

J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London,2000. ; A. Benhocine. Pancyclism and Meyniel’s conditions. Discrete Math., 58:113–120, 1986. ; J.-C. Bermond and C. Thomassen. Cycles in digraphs − a survey. J. Graph Theory, 5(1):1–43, 1981. ; J. Bondy and C. Thomassen. A short proof of Meyniel’s theorem. Discrete Math., 19:195–197, 1977. ; S. Darbinyan. On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis. In Proc-ceedings Conference Computer Science and Information Tecnologies, (CSIT 2015). Yerevan, 2015, pp.53-63. doi: 10.1109/CSITechnol.2015.7358250. ; S. Darbinyan. On pancyclic digraphs. Preprint of the Computing Center of Akademy of Sciences ofArmenia, 1979. ; S. Darbinyan. Disproof of a conjecture of Thomassen. Akad. Nauk Armyan. SSR Dokl., 76(2):51–54,1983. ; S. Darbinyan. Pancyclicity of digraphs with the Meyniel condition. Studia Sci. Math. Hungar., (Ph.D.Thesis, Institute Mathematici Akad. Nauk BSSR, Minsk, 1981), 20(1-4):95–117, 1985. ; S. Darbinyan. Hamiltonian and strongly Hamilton-connected digraphs. Akad. Nauk Armyan. SSR Dokl.,(for a detailed proof see arXiv: 1801.05166v1, 16 Jan. 2018), 91(1):3–6, 1990. ; S. Darbinyan. On cyclability of digraphs with a Manoussakis’-type condition. Transactions of IIAP NASRA, Mathematical Problems of Computer Science, 47:15–29, 2017. ; S. Darbinyan. Some remarks on Manoussakis conjecture for a digraph to be hamiltonian. Emil ArtinInternational Conference, Yerevan, Armenia, May 27-June 2, pages 39–40, 2018. ; S. Darbinyan. On the Manoussakis conjecture for a digraph to be hamiltonian. Transactions of IIAP NASRA, Mathematical Problems of Computer Science, 51:21–38, 2019. ; S. Darbinyan and I. Karapetyan. On pre-Hamiltonian cycles in Hamiltonian digraphs. Transactions ofIIAP NAS RA, Mathematical Problems of Computer Science, 43:5–25, 2015. ; A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien. C. R. Acad. Sci. ParisSer. A-B, 251:495–497, 1960. ; R. Häggkvist and C. Thomassen. On pancyclic digraphs. J. Combin. Theory Ser.B, 20:20–40, 1976. ; F. Harary and L.Moser. The theory of round robin tournaments. Amer.Math.Monthly, 73:231–246, 1966. ; D. Kühn and D. Osthus. A survey on Hamilton cycles in directed graphs. European J. Combin., 33:750–766, 2012. ; H. Li, E. Flandrin, and J. Shu. A sufficient condition for cyclability of directed graphs. Discrete math.,307:1291–1297, 2007. ; Y. Manoussakis. Directed hamiltonian graphs. J. Graph Theory, 16(1):51–59, 1992. ; M. Meyniel. Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente. J.Combin. Theory Ser.B, 14:137–147, 1973. ; C. S. J. A. Nash-Williams. Hamilton circuits in graphs and digraphs, the many facets of graph theory.Springer Verlag Lecture Notes, 110:237–243, 1969. ; B. Ning. Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs. InformationProcessing Letters, 115:221–224, 2015. ; O. Ore. Note on Hamilton circuits. Amer. Math. Monthly, 67:55, 1960. ; D. Woodall. Sufficient condition for circuits in graphs. Proc. London Math. Soc., 24:739–755, 1972. ; A. Yeo. How close to regular must a semicomplete multipartite digraph to be secure hamiltonicity?Graphs Combin., 15:481–493, 1999.

Indexing:

DBLP ; DOAJ ; MathSciNet ; Research Gate ; Scimago ; ZentralBlatt