On cycles in directed graphs
作者： Luke Tristian Kelly
DOI:
关键词:
摘要: The main results of this thesis are the following. We show that for each alpha > 0 every sufficiently large oriented graph G with minimum indegree and outdegree at least 3 |G| / 8 + contains a Hamilton cycle. This gives an approximate solution to problem Thomassen. Furthermore, answering completely conjecture Haggkvist Thomason, we get possible orientation also deal extensively short cycles, showing l 4 1 l-cycle. is best all those which not divisible by 3. Surprisingly, some other values l, l-cycle forced much weaker degree condition. propose discuss regarding precise forces (with 3) in graph. give application our pancyclicity.
bl.uk参考文章(62)
John W. Moon, Topics on tournaments ,(1968)
A. M. Frieze, ON MATCHINGS AND HAMILTON CYCLES IN RANDOM GRAPHS ,(1988)
Gregory Z. Gutin, Jrgen Bang-Jensen, Digraphs: Theory, Algorithms and Applications ,(2002)
Miklos Simonovits, Janos Komlos, Szemeredi''s Regularity Lemma and its applications in graph theory Center for Discrete Mathematics & Theoretical Computer Science. ,(1995)
Melvyn B. Nathanson, The Caccetta-Haggkvist conjecture and additive number theory arXiv: Combinatorics. ,(2006)
Mehdi Behzad, Gary Chartrand, Curtiss Wall, On minimal regular digraphs with given girth Fundamenta Mathematicae. ,vol. 69, pp. 227- 231 ,(1970) , 10.4064/FM-69-3-227-231
Arthur H. Busch, A Note on the Number of Hamiltonian Paths in Strong Tournaments Electronic Journal of Combinatorics. ,vol. 13, pp. 3- ,(2006) , 10.37236/1141
Deryk Osthus, Daniela Kühn, Embedding large subgraphs into dense graphs arXiv: Combinatorics. pp. 137- 168 ,(2009) , 10.1017/CBO9781107325975.007
Tsuyoshi Nishimura, Short cycles in digraphs Discrete Mathematics. ,vol. 72, pp. 295- 298 ,(1988) , 10.1016/0012-365X(88)90219-1
A.M Frieze, An algorithm for finding Hamilton cycles in random directed graphs Journal of Algorithms. ,vol. 9, pp. 181- 204 ,(1988) , 10.1016/0196-6774(88)90037-5