The robust component structure of dense regular graphs and applications
The robust component structure of dense regular graphs and applications
复制标题
稠密正则图的稳健组件结构及应用
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Katherine Staden
中科院分区：
文献类型：
--
作者：
D. Kühn;A. Lo;Deryk Osthus;Katherine Staden
本文研究了稠密正则图的大规模结构。这涉及到稳健扩张的概念，这是一个最近的概念，已经成功地用于解决几个长期存在的问题。粗略地说，如果一个图在删除一小部分顶点和边后仍然膨胀，则该图是鲁棒膨胀的。我们的主要结果使我们能够利用强大的扩张的有用的后果，即使图本身不是一个强大的扩展。它指出，每一个稠密正则图可以划分成“鲁棒组件”，每个组件是一个鲁棒扩展或二部鲁棒扩展。我们应用我们的结果来获得（除其他外）以下内容。我们证明了当ε>0时，每个具有D <$（14+ε）n的n阶3连通D正则图都是Hamilton图.这渐近地证实了Bollobás和Häggkvist在20世纪70年代独立提出的猜想的唯一剩余情况。我们证明了一个渐近最好的可能结果的圆周稠密正则图给定的连通性。这一问题的2连通情形由邦迪提出并由魏明生证明。
In this paper, we study the large‐scale structure of dense regular graphs. This involves the notion of robust expansion, a recent concept which has already been used successfully to settle several longstanding problems. Roughly speaking, a graph is robustly expanding if it still expands after the deletion of a small fraction of its vertices and edges. Our main result allows us to harness the useful consequences of robust expansion even if the graph itself is not a robust expander. It states that every dense regular graph can be partitioned into ‘robust components’, each of which is a robust expander or a bipartite robust expander. We apply our result to obtain (amongst others) the following. We prove that whenever ε>0 , every sufficiently large 3 ‐connected D ‐regular graph on n vertices with D⩾(14+ε)n is Hamiltonian. This asymptotically confirms the only remaining case of a conjecture raised independently by Bollobás and Häggkvist in the 1970s. We prove an asymptotically best possible result on the circumference of dense regular graphs of given connectivity. The 2 ‐connected case of this was conjectured by Bondy and proved by Wei.
有向图中的哈密顿度序列
DOI：
10.48550/arxiv.0807.1827
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Kühn D
通讯作者：
Kühn D