Counting and packing Hamilton cycles in dense graphs and oriented graphs
Counting and packing Hamilton cycles in dense graphs and oriented graphs
复制标题
在密集图和有向图中计算和打包汉密尔顿循环
DOI：
10.1016/j.jctb.2016.06.001
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Asaf Ferber;Michael Krivelevich;B. Sudakov
我们提出了一个一般的方法来计算和包装汉密尔顿圈在稠密图和有向图，永久估计的基础上。我们利用这种方法来证明几个极值结果。特别地，我们证明了每一个c> 3/8的n阶几乎cn-正则定向图都含有（cn/e）n（1+ o（1））n个有向汉密尔顿圈.这是一个扩展的结果Cuckler，谁解决了一个老猜想的Alassen关于数量的汉密尔顿周期定期比赛。我们还证明了：每个最小度至少为（1/2+ o（1））n的n阶图G至少包含（1− o（1））个reg even（G）/2个边不相交的汉密尔顿圈，其中reg even（G）是G的生成正则子图的最大偶度.这建立了一个近似版本的猜想库恩，Lapinskas和Osthus。
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/8 contains (c n/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 contains at least (1− o (1)) reg even (G)/2 edge-disjoint Hamilton cycles, where reg even (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.
登录
查看更多内容
DOI：
10.1112/jlms/jdn065
发表时间：
2008-01
期刊：
Journal of the London Mathematical Society
影响因子：
--
作者：
Peter Keevash;D. Kühn;Deryk Osthus
通讯作者：
Peter Keevash;D. Kühn;Deryk Osthus
DOI：
10.1016/j.jctb.2011.10.005
发表时间：
2009-08
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Demetres Christofides;D. Kühn;Deryk Osthus
通讯作者：
Demetres Christofides;D. Kühn;Deryk Osthus
高最小次数图中哈密顿循环的最优堆积
DOI：
10.1017/s0963548312000569
发表时间：
2012
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
KÜHN D
通讯作者：
KÜHN D
关于稀疏随机图中的哈密顿循环数
DOI：
10.1137/120884316
发表时间：
2013
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
R. Glebov;M. Krivelevich
通讯作者：
M. Krivelevich
有向图中的哈密顿度序列
DOI：
10.48550/arxiv.0807.1827
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Kühn D
通讯作者：
Kühn D