Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups
type: Item
instance of: scholarly article
title: Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups
zbMATH Open document ID: 0869.05046
DOI: 10.1016/0012-365X(95)00035-U
author: Cong Fan
author: Don R. Lick
author: Jiuqiang Liu
published in: Discrete Mathematics
publication date: 1997-08-14T00:00:00Z
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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 943218
zbMATH Keywords: Hamilton decomposition
zbMATH Keywords: Cayley graph
zbMATH Keywords: abelian group
reviewed by: Brian Alspach
MaRDI profile type: Publication
cites work: Q3197858
cites work: Décomposition de la somme cartesienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens
cites work: Hamiltonian decomposition of Cayley graphs of degree 4
cites work: Q3818315
cites work: Hamiltonian decompositions of products of cycles
cites work: Q4004378
cites work: Hamiltonian decompositions of Cayley graphs on Abelian groups
cites work: Hamiltonian decompositions of Cayley graphs on abelian groups of odd order
cites work: Hamiltonian circuits in Cayley graphs
cites work: Hamilton decompositions of Cartesian products of graphs
description: scientific article; zbMATH DE number 943218