On pre-Hamiltonian Cycles in Hamiltonian Digraphs
Keywords:
Digraphs, Cycles, Hamiltonian cycles, Pre-Hamiltonian cycles, Longest non-Hamiltonian cyclesAbstract
Let D be a strongly connected directed graph of order n ≥ 4. In [14] (J. of Graph Theory, Vol.16, No. 5, 51-59, 1992) Y. Manoussakis proved the following theorem: Suppose that D satisfies the following condition for every triple x, y, z of vertices such that x and y are nonadjacent: If there is no arc from x to z, then d(x)+d(y)+d +(x)+ d ¡(z) ≥ 3n–2. If there is no arc from z to x, then d(x)+d(y)+d ¡(x)+d +(z) ¸ 3n¡2. Then D is Hamiltonian. In this paper we show that: If D satisfies the condition of Manoussakis' theorem, then D contains a pre-Hamiltonian cycle (i.e., a cycle of length n ¡ 1) or n is even and D is isomorphic to the complete bipartite digraph with partite sets of cardinalities n=2 and n=2.
References
J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2 000.
J. Bang-Jensen, G. Gutin and H . Li, “Sufficient conditions for a digraph to be Hamiltonian", Journal of Graph Theory, vol. 22, no. 2, pp. 181-187, 1996.
J. Bang-Jensen, Y. Guo and A.Y eo, “A new sufficient condition for a digraph to be Hamiltonian", Discrete Applied Mathematics, vol. 95, pp. 61-72, 1999.
J. A. Bondy, “Basic graph theory: paths and circuits", In Handbook of combinatorics, vol. 1, no. 2, Elsevier, Amsterdam, 1995.
J. A. Bondy and C. Thomassen, “A short proof of Meyniel's theorem", Discrete Mathematics, vol. 19, no. 1, pp. 195-197, 1977.
S. Kh. Darbinyan, “Pancyclic and panconnected digraphs", Ph.D. Thesis, Institute Mathematici Akademy Nauk BSSR, Minsk, 1981 (see also, Pancyclicity of digraphs with the Meyniel condition, Studia Scientiarum Mathematicarum Hungarica, (in Russian), vol.20, no. 1-4, 95-117, 1985.)
S. Kh. D arbinyan, “A sufficient condition for the Hamiltonian property of digraphs with large semidegrees", Akademy Nauk Armyan. SSR Doklady, vol. 82, no. 1, pp. 6-8, 1986. (see also arXiv: 1111.1843v1 [math.CO] 8 N ov 201 1 ).
S. Kh. Darbinyan, “On the pancyclicity of digraphs with large semidegrees", Akademy Nauk Armyan. SSR Doklady, vol. 83, no.4, pp. 99-101, 1986. (see also arX iv: 1111.1841 v1 [math.CO] 8 N ov 201 1 ).
S.Kh. Darbinyan and I.A. Karapetyan, “On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li", Preprint available at htte: arXiv 1207.5643v2 [math.CO], 20 Sep 2012.
S. Kh. Darbinyan and I.A. Karapetyan, “A note on long non-Hamiltonian cycles in one class of digraphs", Preprint available at htte: arXiv 1209.4456v1 [math.CO], 20 Sep 2012.
R. Häggkvist and C. Thomassen, “On pancyclic digraphs", Journal Combinatorial Theory Ser. B, vol. 20, no. 1, pp. 20-40, 1976.
A. Ghouila-Houri, “U ne condition suffisante d'existence d'un circuit hamiltonien", Comptes Rendus de I' Academie des Sciences P aris Ser. A-B, vol.??, no. 25, pp. 495-497, 1960.
G. Gutin, “Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs", Discrete Mathematics, vol.141 , pp. 153-162, 1995.
Y. Manoussakis, “Directed Hamiltonian graphs", Journal of Graph Theory, vol. 16, no. 1, pp. 51-59, 1992.
M. Meyniel, “Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe oriente", Journal Combinatorial Theory Ser. B, vol. 14, pp. 137-147, 1973.
C. Thomassen, “An Ore-type condition implying a digraph to be pancyclic", Discrete Mathematics, vol.19, no 1, pp.85-92, 1977.
C. Thomassen, “Long cycles in digraphs", Proceeding London Mathematical Society, vol. 3, no. 42, pp. 231-251, 1981.
D. R. Woodall, "Sufficient conditions for circuits in graphs", Proceeding London Mathematical Society, no. 24, pp. 739-755, 1972.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
