On an Extension of the Ghouila-Houri Theorem
DOI:
https://doi.org/10.51408/1963-0089Keywords:
Digraphs, Hamiltonian cycles, Hamiltonian-connected, 2-strongAbstract
Let D be a 2-strong digraph of order n ≥ 8 such that for every vertex x ∈ V(D)\{z}, d(x) ≥ n and d(z) ≥ n − 4, where z is a vertex in V(D). We prove that:
If D contains a cycle passing through z of length equal to n − 2, then D is Hamiltonian.
We also give a new sufficient condition for a digraph to be Hamiltonian-connected.
References
J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2000.
J.-C. Bermond and C. Thomassen, “Cycles in digraphs – A survey”, Journal of Graph Theory, vol. 5, no. 1, pp. 1-43, 1981.
D. Kühn and D. Osthus, “A survey on Hamilton cycles in directed graphs”, European Journal of Combinatorics, vol. 33, pp. 750-766, 2012.
A. Ghouila-Houri, “Une condition suffisante d’existence d’un circuit hamiltonien”, Comptes Rendus de I’Academie des Sciences Paris, ser. A-B 251, pp. 495-497, 1960.
M. Meyniel, “Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente”, Journal of Combinatorial Theory, Ser. B, vol. 14, pp. 137-147, 1973.
C.St.J.A. Nash-Williams, “Hamilton circuits in graphs and digraphs”, The many facets of graph theory, Springer Verlag Lecture Notes 110, (Springer Verlag) pp. 237-243, 1969.
C. Thomassen, “Long cycles in digraphs”, Proceedings of London Mathematical Society, vol. 42, no. 3, pp. 231-251, 1981.
S.Kh. Darbinyan, “Cycles of any length in digraph with large semi-degrees”, Aakdemy Nauk Armyan SSR Doklady, (arXiv.1911.05998v1) vol. 75, no. 4, pp. 147-152, 1982.
C. Thomassen, “Long cycles in digraphs with constraints on degrees, Survey in Combinatorics”, Proc. 7th British Combinatorial Conf., London Math. Soc. Lecture Notes, Cambridge University Press, vol. 38, pp. 211-228, 1979.
S.Kh. Darbinyan, “Hamiltonian and strongly Hamilton-Connected digraphs”, Aakdemy Nauk Armyan SSR Doklady, (arXiv.1801.05166v1), vol. 91, no. 1, pp. 3-8, 1990.
M.K. Goldberg, L.P. Levitskaya and L.M. Satanovskiy, “On one strengthening of the Ghouila-Houri theorem”, Vichislitelnaya Matematika i Vichislitelnaya Teknika, vol. 2, pp. 56-61, 1971.
S.Kh. Darbinyan, “A sufficient condition for a digraph to be Hamiltonian”, Aakdemy Nauk Armyan SSR Doklady, vol. 91, no. 2, pp. 57-59, 1990.
R. Häggkvist and C. Thomassen, “On pancyclic digraphs”, Journal of Combinatorial Theory, Ser. B, vol. 20, no. 1, pp. 20-40, 1976.
J.A. Bondy and C. Thomassen, “A short proof of Meyniel’s theorem”, Discrete Mathematics, vol. 19, pp. 195-197, 1977.
M. Overbeck-Larisch, “Hamiltonian pats in oriented graphs”, Journal of Combinatorial Theory, Ser. B, vol. 21, pp. 76-80, 1976.
R.J. Gould, “Resent Advances on the Hamiltonian Problem: Survey III", Graphs and Combinatorics, vo l. 30, pp. 1-46, 2014.
S.Kh. Darbinyan, “Disproof of a conjecture of Thomassen", Aakdemy Nauk Armyan SSR Doklady, vol. 76, no. 2, pp. 51-54, 1983.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Samvel Kh. Darbinyan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
