Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups

DOI10.1016/0012-365X(95)00035-UMaRDI QIDQ1815310zbMATH OpenFDO

Authors Cong Fan, Don R. Lick, Jiuqiang Liu

Publication date 14 August 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00035-U

zbMATH Keywords

abelian groupCayley graphHamilton decomposition

Mathematics Subject Classification ID

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

Review text

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 Hamilton 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 connection set \(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 authors consider 6-regular Cayley graphs on abelian groups. They obtain Hamilton decompositions for a variety of conditions on the connection sets. The conditions cover `most' cases. In the process of establishing their results, they include a complete proof of the 4-regular case and prove that pseudo-Cartesian products of two cycles have Hamilton decompositions.

Recommendations

• Hamiltonian decompositions of Cayley graphs on abelian groups of odd order
• A note on Hamiltonian decompositions of Cayley graphs
• Hamilton decompositions of certain 6-regular Cayley graphs on abelian groups with a cyclic subgroup of index two
• Hamiltonian decompositions of Cayley graphs on abelian groups of even order
• Hamilton decompositions of 6-regular Cayley graphs on even abelian groups with involution-free connections sets

Cites work

• Décomposition de la somme cartesienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens
• Hamilton decompositions of Cartesian products of graphs
• Hamiltonian circuits in Cayley graphs
• Hamiltonian decomposition of Cayley graphs of degree 4
• Hamiltonian decompositions of Cayley graphs on Abelian groups
• Hamiltonian decompositions of Cayley graphs on abelian groups of odd order
• Hamiltonian decompositions of products of cycles
• scientific article; zbMATH DE number 4173021 (Why is no real title available?)
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 54194 (Why is no real title available?)

Cited in

(12)

• 6-regular Cayley graphs on abelian groups of odd order are Hamiltonian decomposable
• Hamiltonian decompositions of Cayley graphs on abelian groups of even order
• On two generalized connectivities of graphs
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Vertex-transitive graphs that have no Hamilton decomposition
• A conjecture of Norine and Thomas for abelian Cayley graphs
• scientific article; zbMATH DE number 6684682 (Why is no real title available?)
• Hamilton decompositions of 6-regular Cayley graphs on even abelian groups with involution-free connections sets
• On Hamilton decompositions of infinite circulant graphs
• Tree connectivities of Cayley graphs on abelian groups with small degrees
• Hamilton decompositions of certain 6-regular Cayley graphs on abelian groups with a cyclic subgroup of index two
• On Hamilton cycle decomposition of 6-regular circulant graphs

This page was built for publication: Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1815310)