On Long Cycles in Digraphs with the Meyniel-type Conditions
Abstract
We shall assume that the reader is familiar with the standard terminology on directed graphs (digraphs) and use Bang-Jensen and Gutin [1] as reference for undefined terms. In this paper we consider finite digraphs without loops and multiple arcs. The subdigraph of D induced by a subset A of V(D) is denoted by (A). We will denote the complete bipartite digraph with partite sets of cardinalities p, q by K*p,q.
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 22 (2) (1996) 181-187.
J. Bang-Jensen, Y. Guo, A. Yeo, A new sufficient condition for a digraph to be hamiltonian, Discrete Applied Math., 95 (1999) 77-87.
J. Bang-Jensen, Y. Guo, L. Volkmann, A classication of locally semicomplete digraphs. 15th British Combinatorial Conference (Stirling, 1995). Discrete Math. 167/168 (1997) 101-114.
J.A. Bondy, C. Thomassen, A short proof of Meyniel's theorem, Discrete Math. 19 (1977) 195-197.
S.Kh. Darbinyan, Pancyclic and panconnected digraphs, Ph. D. Thesis, Institute Mathematici Akad. Nauk BSSR, Minsk, 1981.
S.Kh. Darbinyan, A sufficient condition for the Hamiltonian property of digraphs with large semidegrees, Akad. Nauk Armyan. SSR Dokl. 82 (1) (1986) 6-8.
S.Kh. Darbinyan, On the pancyclicity of digraphs with large semidegrees, Akad. Nauk Armyan. SSR Dokl. 83 (3) (1986) 99-101.
R. Häggkvist, C. Thomassen, On pancyclic digraphs, J. Combin. Theory Ser. B20 (1976) 20-40.
A. Ghouila-Houri, Une condition suffisante d'existence d'un circuit hamiltonien, C.R. Acad. Sci. Paris Ser. A-B 251 (1960) 495-497.
M. Meyniel, Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe oriente, J. Combin. Theory Ser. B 14 (1973) 137-147.
M. Overbeck-Larisch, Hamiltonian paths in oriented graphs, J. Combin. Theory Ser. B21 (1) (1976) 76-80.
C. Thomassen, An Ore-type condition implying a digraph to be pancyclic, Discrete Math. 19 (1) (1977) 85-92.
C. Thomassen, Long cycles in digraphs, Proc. London Math. Soc. (3) 42 (1981) 231-251.
D.R. Woodall, Sufficient conditions for circuits in graphs, Proc. London Math. Soc. 24 (1972) 739-755.
Pancyclicity of digraphs with the Meyniel condition, Studia Sci. Math. Hungar., 20 (1-4) (1985) 95-117, in Russian.
arXiv: 1111.1843v1 [math.CO] 8 Nov 2011.
arXiv: 1111.1841v1 [math.CO] 8 Nov 2011.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
