On Cyclability of Digraphs with a Manoussakis-type
Keywords:
Digraphs, Cycles, Hamiltonian cycles, CyclabilityAbstract
Let D be a digraph of order n ¸ 4 and Y be a non-empty subset of vertices of D. Let for any pair u, v of distinct vertices of Y the digraph D contain a path from u to v and a path from v to u. Suppose D satis¯es the following conditions for every triple x; y; z 2 Y 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 +(z) + d ¡(x) ¸ 3n ¡ 2. We prove that there is a directed cycle in D which contains all the vertices of Y , except possibly one. This result is best possible in some situations and gives an answer to a question of Li, Flandrin and Shu (Discrete Mathematics, 307 (2007) 1291-1297).
References
B. Bollobas, G. Brightwell, "Cycles through specified vertices", Combinatorica, vol. 13, no. 2, pp. 117-155, 1993
K. Ota, "Cycles through prescribed vertices with large degree sum", Discrete Mathematics, vol. 14, pp. 201-210, 1995
R. Shi,"2-Neighbourhood and hamiltonian conditions", Journal of Graph Theory 16, pp. 267-271, 1992
H.J. Veldman, "Cycles containing many vertices of large degree", Discrete Mathematics, vol. 101, pp. 319-325, 1992
H. Li, E. Flandrin and J. Shu, "A sufficient condition for cyclability in directed graphs", Discrete Mathematics, vol. 307, pp. 1291-1297, 2007
M. Meyniel, "Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente, Journal of Combinatorial Theory B, vol. 14, pp. 137-147, 1973
A. Ghouila-Houri, "Une condition suffisante d'existence d'un circuit hamiltonien", C. R. Acad. Sci. Paris A-b, vol. 251, pp. 495-497, 1960
D.R. Woodall, "Sufficient conditions for circuits in graphs", Proceeding London Mathematical Society, vol. 24, pp. 739-755, 1972
J. A. Bondy and C. Thomassen, "A short proof of Meyniel's theorem", Discrete Mathematics, vol. 19, pp. 195-197, 1977
D. B. West, Introduction to Graph Theory, Pretice-Hall, New Delhi, 2001
S. Kh. Darbinyan, "A sufficient condition for the Hamiltonian property of digraphs with large semidegrees", Akademy Nauk Armyan. SSR Dokl., vol. 82, no. 1, pp. 6-8, 1986 (see also arXiv: 1111.1843v1 [math.CO] 8 Nov 2011)
K. A. Berman and X. Liu, "Cycles through large degree vertices in digraphs: A generalization of Meyniel's theorem", it Journal of Combinatorial Theory B, vol. 74, pp. 20-27, 1998
Y. Manoussakis, "Directed Hamiltonian graphs", Journal of Graph Theory, vol. 16, no. 1, pp. 51-59, 1992
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. Yeo, "A new sufficient condition for a digraph to be Hamiltonian", Discrete Applied Mathematics, vol. 95, pp. 77-87, 1999
J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2001
R. Haeggkvist and C. Thomassen, "On pancyclic digraphs", Journal of Combinatorial Theory B, vol. 20, pp. 20-40, 1976
C. Thomassen, "Long cycles in digraphs", Proceeding London Mathematical Society, vol. 3, no. 42, pp. 231-251, 1981
S. Kh. Darbinyan, "A sufficient condition for the Hamiltonian property of digraphs with large semidegrees", Akademy Nauk Armyan. SSR Dokl., vol. 82, no. 1, pp. 6-8, 1986 (see also arXiv: 1111.1843v1 [math.CO] 8 Nov 2011)
S. Kh. Darbinyan and I.A. Karapetyan, "On cycles through vertices of large semidegree in digraphs", Mathematical Problems of Computer Science, vol. 39, pp.106-118, 2013
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
