zbMATH — the first resource for mathematics

Hamiltonian decompositions of Cayley graphs on abelian groups of odd order. (English) Zbl 0840.05069
The reviewer has posed the problem [Research Problem 59, Discrete Math. 50, 115 (1984)] of whether or not every connected Cayley graph on a finite abelian group has a Hamiltonian decomposition, that is, a partition of the edge set into Hamilton cycles. The Cayley graph \(X(G; S)\) on the finite abelian group \(G\) with symbol \(S\) is the graph whose vertices are labelled by the elements of \(G\) with an edge joining \(x\) and \(y\) if and only if either \(x- y\) or \(y- x\) belongs to \(S\). With this definition, it is assumed that \(s\in S\) and \(\text{ord}(s)\neq 2\) imply \(s^{-1}\not\in S\). The author proves that a Cayley graph \(X(G; S)\) on an odd order abelian group \(G\) has a Hamilton decomposition whenever \(S\) is a minimal generating set of \(G\).

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX Cite
Full Text: DOI