zbMATH — the first resource for mathematics

Hamiltonian decomposition of Cayley graphs of degree 4. (English) Zbl 0618.05032
We prove that any 4-regular connected Cayley graph on a finite abelian group can be decomposed into two hamiltonian cycles. This answers a partial case of Alspach’s conjecture concerning hamiltonian decompositions of 2k-regular connected Cayley graphs. As corollary we obtain the hamiltonian decomposition of 2-jump circulant graphs, called also double loops.

05C38 Paths and cycles
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Full Text: DOI
[1] Alspach, B, Unsolved problem 4.5, Ann. discrete math., 27, 464, (1985)
[2] Aubert, J; Schneider, B, Decomposition de la somme cartésienne d’un cycle et de l’union de deux cycles hamiltoniens en cycles hamiltoniens, Discrete math., 38, 7-16, (1982) · Zbl 0475.05057
[3] Bermond, J.-C, Hamiltonian décomposition of graphs and hypergraphs, (), 21-28 · Zbl 0382.05040
[4] Bermond, J.-C; Illiades, G; Peyrat, C, An optimization problem in distributed loop computer networks, (), in press · Zbl 0727.68088
[5] Boesch, F; Tindell, R, Circulants and their connectivities, J. graph theory, 8, 487-499, (1984) · Zbl 0549.05048
[6] {\scC. Delorme, O. Favaron, and M. Maheo}, Isomorphisms of Cayley multigraphs of degree 4 on finite abelian groups, submitted for publication. · Zbl 0759.05044
[7] Foregger, M.F, Hamiltonian decompositions of product of cycles, Discrete math., 24, 251-260, (1978) · Zbl 0398.05055
[8] Huang, Yixiu, On Hamiltonian decompositions of Cayley graphs on cyclic groups, () · Zbl 0793.05068
[9] Soaping, Loo, Some results about circulant graphs, ()
[10] Sun, Liang, Some results on circulant graphs, () · Zbl 0890.05039
[11] Witte, D; Gallian, J.A, A survey: Hamiltonian cycles in Cayley graphs, Discrete math., 51, 293-304, (1984) · Zbl 0712.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.