Erde Joshua, Lehner Florian
Institute of Discrete Mathematics Graz University of Technology Graz Austria.
J Graph Theory. 2022 Nov;101(3):559-571. doi: 10.1002/jgt.22840. Epub 2022 May 9.
A well-known conjecture of Alspach says that every -regular Cayley graph of a finite abelian group can be decomposed into Hamiltonian cycles. We consider an analogous question for infinite abelian groups. In this setting one natural analogue of a Hamiltonian cycle is a spanning double-ray. However, a naive generalisation of Alspach's conjecture fails to hold in this setting due to the existence of -regular Cayley graphs with finite cuts , where and differ in parity, which necessarily preclude the existence of a decomposition into spanning double-rays. We show that every 4-regular Cayley graph of an infinite abelian group all of whose finite cuts are even can be decomposed into spanning double-rays, and so characterise when such decompositions exist. We also characterise when such graphs can be decomposed either into Hamiltonian circles, a more topological generalisation of a Hamiltonian cycle in infinite graphs, or into a Hamiltonian circle and a spanning double-ray.
阿尔斯帕奇的一个著名猜想指出，有限阿贝尔群的每个(k -)正则凯莱图都可以分解为哈密顿圈。我们考虑无限阿贝尔群的一个类似问题。在此情形下，哈密顿圈的一个自然类似物是生成双射线。然而，由于存在具有有限割集(S)的(k -)正则凯莱图，其中(|S|)和(k)奇偶性不同，阿尔斯帕奇猜想的一个简单推广在此情形下不成立，这必然排除了分解为生成双射线的可能性。我们证明，每个有限割集均为偶数的无限阿贝尔群的(4 -)正则凯莱图都可以分解为生成双射线，从而刻画了此类分解存在的条件。我们还刻画了此类图何时可以分解为哈密顿圆（无限图中哈密顿圈的一种更具拓扑性的推广），或者分解为一个哈密顿圆和一条生成双射线。
