On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs
Keywords:
Digraphs, Cycles, Hamiltonian cycles, Hamiltonian bypassesAbstract
Let D be a strongly connected directed graph of order n ≥ 4 which satisfies the following condition (*): for every pair of non-adjacent vertices x, y with a common in-neighbour d(x) + d(y) ≥ 2n - 1 and min {d(x), d(y)} ≥ n - 1. In [2] (J. of Graph Theory 22 (2) (1996) 181-187)) J. Bang-Jensen, G. Gutin and H. Li proved that D is Hamiltonian. In [9] it was shown that if D satisfies the condition (*) and the minimum semi-degree of D at least two, then either D contains a pre-Hamiltonian cycle (i.e., a cycle of length n - 1) or n is even and D is isomorphic to complete bipartite digraph (or to complete bipartite digraph minus one arc) with equal partite sets. In this paper we show that if the minimum out-degree of D at least two and the minimum in-degree of D at least three, then D contains also a Hamiltonian bypass, (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc).
References
J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2000.
J. Bang-Jensen, G. Gutin, 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, A.Yeo, “A new sufficient condition for a digraph to be Hamiltonian", Discrete Applied Mathematics, vol. 95, pp. 77-87, 1999.
A.Benhocine, “On the existence of a specified cycles in digraphs with constraints on degrees", Journal of Graph Theory, vol. 8, pp.101 -107, 1984.
J.A. Bondy, C. Thomassen, “A short proof of Meyniel's theorem", Discrete Mathematics, vol. 19, no. 1, pp. 85-92, 1977.
S.Kh. Darbinyan, "A sufficient condition for the Hamiltonian property of digraphs with large semidegrees", Akademy Nauk Armyan. SSR Doklady, (see also arXiv: 1111.1843v1 [math.CO] 8 Nov 2011), vol. 82, no. 1, pp.6-8, 1986.
S.Kh. D arbinyan, “On Hamiltonian bypasses in digraphs satisfying Meyniel-like conditions", Mathematical Problems in Computer Science, (see also Proceedings of 5-th science-technical conference for yang researchers, p. 23, Tsaghkadzor, Armenia, 1986), ( in Russian), vol. 20, pp.7-19, 1998.
S.Kh. Darbinyan, “On the specified cycles in oriented graphs", Akademy Nauk Armyan. SSR Doklady, (in Russian), vol. 84, no. 1, pp. 51-55, 1987.
S.Kh. Darbinyan, 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, I. A. Karapetyan, “A note on long non-Hamiltonian cycles in one class of digraphs", P reprint available at htte: arXiv 1209.4456v1 [math.CO], 20 Sep 2012.
R. Häggkvist, C. Thomassen, “On pancyclic digraphs", Journal Combinatorial Theory Ser. B, vol. 20, pp. 20-40, 1976.
A. Ghouila-Houri, “Une condition suffisante d'existence d'un circuit hamiltonien", Comptes Rendus de I'Academie des Sciences Paris Ser. A-B, no. 251, pp. 495-497, 1960.
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.St.J.A. Nash-Williams, “Hamilton circuits in graphs and digraphsit. The many facts of graph theory", Springer Lecture Notes. 110, pp.237-243, 1969.
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.
