On the Manoussakis Conjecture for a Digraph to be Hamiltonian
DOI:
https://doi.org/10.51408/1963-0031Keywords:
Digraph, Hamiltonian cycle, Cycle factor, Pancyclic digraphAbstract
Manoussakis (J. Graph Theory 16, 1992, 51-59) 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) ≥ 4n − 3. Then D is Hamiltonian. In this note, we prove that if D satisfies the conditions of this conjecture, then (i) D has a cycle factor; (ii) If {x, y} is a pair of non-adjacent vertices of D such that d(x) + d(y) ≤ 2n − 2, then D is Hamiltonian if and only if D contains a cycle passing through x and y; (iii) If {x, y} a pair of non-adjacent vertices of D such that d(x)+d(y) ≤ 2n−4, then D contains cycles of all lengths 3, 4, . . . , n−1; (iv) D contains a cycle of length at least n − 1
References
J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, SpringerVerlag, London, 2000.
J.-C. Bermond and C. Thomassen, “Cycles in digraphs- A survey”, J. Graph Theory, vol. 5, pp.1-43, 1981.
D. K¨uh and D. Ostus, “A survey on Hamilton cycles in directed graphs”, European J. Combin., vol. 33, pp. 750-766, 2012.
M. Meyniel, “Une condition suffisante d’existence d’un circuit Hamiltonien dans un graphe oriente”, J. Combinatorial Theory B, vol. 14, pp. 137-147, 1973.
Y. Manoussakis, “Directed Hamiltonian graphs”, J. Graph Theory, vol. 16, no. 1, pp. 51-59, 1992.
S. Kh. Darbinyan, “Disproof of a conjecture of Thomassen”, Akad. Nauk Armyan. SSR Dokl., vol. 76, no. 2, pp. 51-54, 1983.
S. Kh. Darbinyan, “On Hamiltonian and Hamilton-connected digraphs”, Akad. Nauk Armyan. SSR Dokl., vol. 91, no. 1, pp. 3-6, 1990 (for a detailed proof see arXiv: 1801.05166v1, 16 Jan 2018.
B. Ning, “Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs, electronic preprint”, arXiv:1404.5013v1 [math.CO] 20 Apr 2014, pp. 8.
R. H¨aggvist and C. Thomassen, “On pancyclic digraphs”,J. Combin. Theory B, vol. 20, pp. 20-40, 1976.
J. A. Bondy and C. Thomassen, “A short proof of Meyniel’s theorem’, Discrete Math., vol. 19, pp. 195-197, 1977.
J. A. Bondy, “Basic Graph Theory: Paths and Circuits”, In Handbook of Combinatorics, vol. 1-2, Elsevier, Amsterdam, 1995.
A.Yeo, “How close to regular must a semicomplete multipartite digraph to be secure Hamiltonisity?”, Graphs Combin., vol. 15, pp. 481-493, 1999.
S. Kh. Darbinyan, “On pancyclic digraphs”, Preprint of the Computing Center of Akademy of Sciences of Armenia, 21 pages, 1979.
S. Kh. Darbinyan, “Pancyclicity of digraphs with the Meyniel condition”, Studia Sci. Math. Hungar., vol. 20, no. 1-4, pp. 95-117, 1985. (Ph.D. Thesis, Institute Mathematici Akad. Nauk BSSR, Minsk, 1981).
A. Benhocine, “Pancyclism and Meyniel’s conditions”, Discrete Math., vol. 58, pp. 113- 120, 1986.
F. Harary and L. Moser, “The theory of round robin tournaments”, Amer. Math. Monthly, vol. 73, pp. 231-246, 1966.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
