#### Title:

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

#### Author:

#### Type:

#### 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:

#### Date submitted:

#### Date accepted:

#### Date modified:

#### Date of publication:

#### DOI:

#### Language:

#### Journal or Publication Title:

Discrete Mathematics & Theoretical Computer Science

#### Volume:

#### Number:

#### URL:

#### Additional Information:

#### Affiliation:

Institute for Informatics and Automation Problems of NAS RA

#### Year:

#### 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