×

A new sufficient condition for a digraph to be Hamiltonian – a proof of Manoussakis conjecture. (English) Zbl 1462.05156

Summary: Y. Manoussakis [J. Graph Theory 16, No. 1, 51–59 (1992; Zbl 0755.05074)] proposed the following conjecture.
Conjecture: Let \(D\) be a 2-strongly connected digraph of order \(n\) such that for all distinct pairs of non-adjacent vertices \(x\), \(y\) and \(w\), \(z\), we have \(d(x)+d(y)+d(w)+d(z)\geq 4n-3\). Then \(D\) is Hamiltonian. 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)\leq 2n-4\), then \(D\) contains cycles of all lengths \(3, 4, \ldots , n\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 0755.05074
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] J. Bang-Jensen and G. Gutin.Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2000. · Zbl 1001.05002
[2] A. Benhocine. Pancyclism and Meyniel’s conditions.Discrete Math., 58:113-120, 1986. · Zbl 0585.05008
[3] J.-C. Bermond and C. Thomassen. Cycles in digraphs−a survey.J. Graph Theory, 5(1):1-43, 1981. · Zbl 0458.05035
[4] J. Bondy and C. Thomassen. A short proof of Meyniel’s theorem.Discrete Math., 19:195-197, 1977. · Zbl 0368.05029
[5] S. Darbinyan. On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis. InProcceedings Conference Computer Science and Information Tecnologies, (CSIT 2015). Yerevan, 2015, pp. 53-63. doi: 10.1109/CSITechnol.2015.7358250.
[6] S. Darbinyan. On pancyclic digraphs.Preprint of the Computing Center of Akademy of Sciences of Armenia, 1979.
[7] S. Darbinyan. Disproof of a conjecture of Thomassen.Akad. Nauk Armyan. SSR Dokl., 76(2):51-54, 1983. · Zbl 0521.05031
[8] 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. · Zbl 0614.05025
[9] 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.
[10] S. Darbinyan. On cyclability of digraphs with a Manoussakis’-type condition.Transactions of IIAP NAS RA, Mathematical Problems of Computer Science, 47:15-29, 2017.
[11] S. Darbinyan. Some remarks on Manoussakis conjecture for a digraph to be hamiltonian.Emil Artin International Conference, Yerevan, Armenia, May 27-June 2, pages 39-40, 2018.
[12] S. Darbinyan. On the Manoussakis conjecture for a digraph to be hamiltonian.Transactions of IIAP NAS RA, Mathematical Problems of Computer Science, 51:21-38, 2019.
[13] S. Darbinyan and I. Karapetyan. On pre-Hamiltonian cycles in Hamiltonian digraphs.Transactions of IIAP NAS RA, Mathematical Problems of Computer Science, 43:5-25, 2015.
[14] A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien.C. R. Acad. Sci. Paris Ser. A-B, 251:495-497, 1960. · Zbl 0091.37503
[15] R. H¨aggkvist and C. Thomassen. On pancyclic digraphs.J. Combin. Theory Ser.B, 20:20-40, 1976. · Zbl 0284.05110
[16] A new sufficient condition for a digraph to be Hamiltonian−A proof of Manoussakis conjecture21
[17] F. Harary and L. Moser. The theory of round robin tournaments.Amer. Math. Monthly, 73:231-246, 1966. · Zbl 0142.41602
[18] D. K¨uhn and D. Osthus. A survey on Hamilton cycles in directed graphs.European J. Combin., 33: 750-766, 2012. · Zbl 1239.05114
[19] H. Li, E. Flandrin, and J. Shu. A sufficient condition for cyclability of directed graphs.Discrete math., 307:1291-1297, 2007. · Zbl 1115.05053
[20] Y. Manoussakis. Directed hamiltonian graphs.J. Graph Theory, 16(1):51-59, 1992. · Zbl 0755.05074
[21] M. Meyniel. Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente.J. Combin. Theory Ser.B, 14:137-147, 1973. · Zbl 0259.05114
[22] 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.
[23] B. Ning. Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs.Information Processing Letters, 115:221-224, 2015. · Zbl 1304.05090
[24] O. Ore. Note on Hamilton circuits.Amer. Math. Monthly, 67:55, 1960. · Zbl 0089.39505
[25] D. Woodall. Sufficient condition for circuits in graphs.Proc. London Math. Soc., 24:739-755, 1972. · Zbl 0233.05117
[26] A. Yeo. How close to regular must a semicomplete multipartite digraph to be secure hamiltonicity? Graphs Combin., 15:481-493, 1999. · Zbl 0939.05059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.