On Hamilton decompositions of infinite circulant graphs
On Hamilton decompositions of infinite circulant graphs
复制标题
DOI：
10.1002/jgt.22223
复制
发表时间：
2018-07-01
影响因子：
0.9
通讯作者：
Webb, Bridget S.
中科院分区：
文献类型：
--
作者：
Bryant, Darryn;Herke, Sarada;Webb, Bridget S.
（有限）Hamilton环的自然无限模拟是双向无限Hamilton路径（连通生成2价子图）。虽然已知每个连通的2k价无限循环图都有一条双向无限Hamilton路径，但是存在许多这样的图，它们并不分解为k条边不相交的双向无限Hamilton路径。这与有限情况形成对比，在有限情况下，我们推测每个2k价连通循环图都分解成k个边不相交的汉密尔顿环。我们解决了k=2时k价无限循环图分解为k条边不相交的双向无限Hamilton路径的问题，当k=3时，在许多其他情况下，包括连接集为+/-{1,2，…，k}或+/-{1,2，…，k-1,k+1}。
The natural infinite analog of a (finite) Hamilton cycle is a two-way-infinite Hamilton path (connected spanning 2-valent subgraph). Although it is known that every connected 2k-valent infinite circulant graph has a two-way-infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge-disjoint two-way-infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k-valent connected circulant graph has a decomposition into k edge-disjoint Hamilton cycles. We settle the problem of decomposing 2k-valent infinite circulant graphs into k edge-disjoint two-way-infinite Hamilton paths for k=2, in many cases when k=3, and in many other cases including where the connection set is +/-{1,2,...,k} or +/-{1,2,...,k-1,k+1}.