On Cycles Through Vertices of Large Semidegree in Digraphs
Keywords:
digraphs, cycles, Hamiltonian cycles, cyclabilityAbstract
Let D be a strong digraph on n = 2m+1 ≥ 5 vertices. In this paper we show that if D contains a cycle of length n—1, then D has also a cycle which contains all vertices with in-degree and out-degree at least m (unless some extremal cases).
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", J. 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 Math, vol. 95, pp. 77-87, 1999.
K.A. Berman, X.Liu, “Cycles through large degree vertices in digraphs: A generalization of Meyniel's theorem", J. Combin. Theory Ser. B, 74, no. 1, pp. 20-27, 1998.
B. Bollobas, G. Brightwell, “Cycles through specified vertices", Combinatorica, vol. 13, no. 2, pp. 117-155, 1993.
J.A. Bondy, C. Thomassen, “A short proof of Meyniel's theorem", Discrete Math, vol. 19, no. 1, pp. 85-92, 1977.
S.Kh. Darbinyan, “A sufficient condition for the Hamiltonian property of digraphs with large semidegrees", Akad. Nauk Armyan. SSR Dokl., vol. 82, no. 1, pp. 6-8, 1986.
arXiv: 1111.1843v1 [math.CO] 8 Nov 2011.
Kh. Darbinyan, “Hamiltonian and strongly Hamilton-connected digraphs", Akad. Nauk Armyan. SSR Dokl, vol. 91, no. 1, pp. 3-6, 1990 (in Russian).
S.Kh. Darbinyan, “A sufficient condition for digraphs to be Hamiltonian", Akad. Nauk Armyan. SSR Dokl, vol. 91, no. 2, pp. 57-59, 1990 (in Russian).
R. Häggkvist, C. Thomassen, “On pancyclic digraphs", J. Combin. Theory Ser. B, vol. 20, pp. 20-40, 1976.
A. Ghouila-Houri, “Une condition suffisante d'existence d'un circuit hamiltonien", C. R. Acad. Sci. Paris Ser. A-B, no. 251, pp. 495-497, 1960.
H. Li, E. Flandrin, J. Shu, “A sufficient condition for cyclability in directed graphs", Discrete Math., vol. 307, pp. 1291-1297, 2007.
Y. Manoussakis, “Directed hamiltonian graphs", J. 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", J. Combin. Theory Ser. B, vol. 14, pp. 137-147, 1973.
K. Ota, “Cycles through prescribed vertices with large degrees um", Discrete Math. vol. 145, pp. 201-210, 1995.
R. Shi, “2-Neighborhoods and hamiltonian conditions", J.Graph Theory, no. 16, pp. 267-271, 1992.
C. Thomassen, “Long cycles in digraphs", Proc. London Math. Soc., vol. 3, no. 42, pp. 231-251, 1981.
H.J. Veldman, “Cycles containing many vertices of large degree", Discrete Math., vol. 101, pp. 319-325, 1992.
D.R. Woodall, Sufficient conditions for circuits in graphs", Proc. London Math. Soc., 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.
