Approximate Hamilton Decompositions of Robustly Expanding Regular Digraphs
Approximate Hamilton Decompositions of Robustly Expanding Regular Digraphs
复制标题
鲁棒扩展正则图的近似哈密尔顿分解
DOI：
10.1137/120880951
复制
发表时间：
2013
影响因子：
0.8
通讯作者：
Osthus D
中科院分区：
文献类型：
--
作者：
Osthus D
我们证明了每一个具有线性度且是鲁棒外扩张的充分大正则有向图都有一个近似分解为边不相交的汉密尔顿圈，即，包含一组边缘不相交的汉密尔顿圈。如果对于每个不太小也不太大的集合，的“鲁棒”外邻居比稍大，则这里有一个鲁棒外扩展器。这推广了Kuehhn，Osthus和Treglown关于稠密正则定向图的近似汉密尔顿分解的一个结果.推广了Frieze和Krivelevich关于拟随机（di）图的近似汉密尔顿分解的一个结果.反过来，我们的结果被Kuehhn和Osthus用作工具，证明了任何具有线性度且是鲁棒外扩的充分大正则有向图都有汉密尔顿分解.
We show that every sufficiently large-regular digraphwhich has linear degree and is a robust outexpander has an approximate decomposition into edge-disjoint Hamilton cycles, i.e.,contains a set ofedge-disjoint Hamilton cycles. Hereis a robust outexpander if for every setwhich is not too small and not too large, the “robust” outneighborhood ofis a little larger than. This generalizes a result of Kühn, Osthus, and Treglown on approximate Hamilton decompositions of dense regular oriented graphs. It also generalizes a result of Frieze and Krivelevich on approximate Hamilton decompositions of quasirandom (di)graphs. In turn, our result is used as a tool by Kühn and Osthus to prove that any sufficiently large-regular digraphwhich has linear degree and is a robust outexpander even has a Hamilton decomposition.
将紧密的哈密尔顿循环封装在 3 均匀超图中
影响因子：
1
作者：
A. Frieze;Michael Krivelevich;Po
通讯作者：
Po
有向图中的哈密顿度序列
DOI：
10.48550/arxiv.0807.1827
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Kühn D
通讯作者：
Kühn D