Hamilton cycles in dense vertex-transitive graphs
Hamilton cycles in dense vertex-transitive graphs
复制标题
密集顶点传递图中的哈密顿循环
DOI：
10.1016/j.jctb.2014.05.001
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Christofides D
中科院分区：
文献类型：
--
作者：
Christofides D
Lovász的一个著名猜想是：每个连通点传递图都含有一条汉密尔顿路，本文在图是稠密且足够大的情况下证明了这个猜想.事实上，我们表明，这样的图包含一个汉密尔顿周期，而且我们提供了一个多项式时间算法找到这样一个周期。
A famous conjecture of Lovász states that every connected vertex-transitive graph contains a Hamilton path. In this article we confirm the conjecture in the case that the graph is dense and sufficiently large. In fact, we show that such graphs contain a Hamilton cycle and moreover we provide a polynomial time algorithm for finding such a cycle.