Counting and packing Hamilton cycles in dense graphs and oriented graphs

详细信息    查看全文

• 作者：Asaf Ferber^a ; ^{asaf.ferber@yale.edu} ; Michael Krivelevich^b ; ¹ ; ^{krivelev@post.tau.ac.il} ; Benny Sudakov^c ; ² ; ^{benjamin.sudakov@math.ethz.ch}
• 关键词：Hamilton cycles ; Oriented graphs ; Packing ; Counting
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：196-220
• 全文大小：526 K
• 卷排序：122

文摘

We present a general method for counting and packing Hamilton cycles in dense graphs and oriented graphs, based on permanent estimates. We utilize this approach to prove several extremal results. In particular, we show that every nearly cn-regular oriented graph on n   vertices with c>3/8c>3/8 contains (cn/e)n(1+o(1))n(cn/e)n(1+o(1))n directed Hamilton cycles. This is an extension of a result of Cuckler, who settled an old conjecture of Thomassen about the number of Hamilton cycles in regular tournaments. We also prove that every graph G on n   vertices of minimum degree at least (1/2+o(1))n(1/2+o(1))n contains at least (1−o(1))regeven(G)/2(1−o(1))regeven(G)/2 edge-disjoint Hamilton cycles, where regeven(G)regeven(G) is the maximum even degree of a spanning regular subgraph of G. This establishes an approximate version of a conjecture of Kühn, Lapinskas and Osthus.