zbMATH — the first resource for mathematics

Hamiltonian decompositions of Cayley graphs on Abelian groups. (English) Zbl 0809.05058
The author considers when the Cayley graph \(\text{cay}(A,S)\), where \((A,+)\) is a group, \(A\) denotes the vertex set and \(S\subseteq A\), \(0\not\in S\), determines the edges of the graph (\(xy\) is an edge if and only if \(x- y\in S\cup- S\)), has a Hamilton decomposition. It is shown that such a decomposition exists: (1) if \(S= \{s_ 1,\dots, s_ k\}\) is a generating set of \(A\) such that \(\text{gcd}(\text{ord}(s_ i), \text{ord}(s_ j))= 1\) for \(i\neq j\), or a minimal generating set of \(A\) with \(k= 3\) and with either two elements of order 2 or one element of prime order; and (2) if \(A\) is an Abelian group of odd order and \(S= \{s_ 1,s_ 2,s_ 3\}\) is a minimal generating set of \(A\).

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] Alspach, B., Research problem 59, Discrete math., 50, 115, (1984)
[2] Alspach, B.; Bermond, J.-C.; Sotteau, D., Decomposition into cycles I: Hamilton decompositions, (), 9-18 · Zbl 0713.05047
[3] Aubert, J.; Schneider, B., Decomposition de la somme cartĂ©sienne d’un cycle et de l’union de deux cycles hamiltonens en cycles hamiltoniens, Discrete math., 38, 7-16, (1982) · Zbl 0475.05057
[4] Bermond, J.-C.; Favaron, O.; Maheo, M., Hamiltonian decomposition of Cayley graphs of degree 4, J. combin. theory ser. B, 46, 142-153, (1989) · Zbl 0618.05032
[5] G. Chartrand and L. Lesniak, Graphs and Diagraphs, 2nd Edition (Wardsworth and Brooks/Cole, Monterey, CA). · Zbl 1057.05001
[6] Foregger, M.F., Hamiltonian decompositions of products of cycles, Discrete math., 24, 251-260, (1978) · Zbl 0398.05055
[7] J.A. Gallian, Contemporary Abstract Algebra (D.C. Heath, Lexington, MA).
[8] Marusic, D., Hamiltonian circuits in Cayley graphs, Discrete math., 46, 49-54, (1983) · Zbl 0515.05042
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.