Hamiltonian decompositions of Cayley graphs on abelian groups of even order

DOI10.1016/S0095-8956(03)00033-9MaRDI QIDQ1400966zbMATH OpenOpenAlexFDO

Authors Jiuqiang Liu

Publication date 17 August 2003

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0095-8956(03)00033-9

zbMATH Keywords

abelian groupCayley graphHamiltonian 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

Let \((A,+)\) be a finite abelian group and \(S\) a subset of \(A\) with \(0\not\in S\). The Cayley graph \(\text{Cay}(A,S)\) is defined to be the graph \(G=(V,E)\) with \(V=A\) and \(E=\{xy\mid x-y\in S\) or \(y-x\in S\}\). Alspach conjectured that any \(2k\)-regular connected Cayley graph on a finite abelian group has a Hamiltonian decomposition, that is, the set of edges admits a partition in \(k\) Hamiltonian circuits [\textit{B. Alspach}, Research problem 59, Discrete Math. 50, 115 (1984)]. J. Liu proved that if \(A\) is an abelian finite group of odd order and \(S\) is a minimal generating set of \(A\), then \(\text{Cay(A,S)}\) has a Hamiltonian decomposition [\textit{J. Liu}, J. Comb. Theory, Ser. B 66, 75-86 (1996; Zbl 0840.05069)]. In this paper the same author shows the following: Let \(A\) be a finite abelian group of even order at least 4 and \(S\) a minimal generating subset of \(A\) such that for any \(s\in S\), the element \(2s\) is not generated by elements in \(S-\{s\}\). Then \(\text{Cay}(A,S)\) has a Hamiltonian decomposition.

Recommendations

• Hamiltonian decompositions of Cayley graphs on abelian groups of odd order
• Hamiltonian decompositions of Cayley graphs on Abelian groups
• Hamiltonian decomposition of Cayley graphs of orders \(p^2\) and \(pq\)
• Hamilton decompositions of 6-regular Cayley graphs on even abelian groups with involution-free connections sets
• Hamilton decompositions of certain 6-regular Cayley graphs on abelian groups with a cyclic subgroup of index two

Cites work

• 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
• Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups

Cited in

(25)

• 6-regular Cayley graphs on abelian groups of odd order are Hamiltonian decomposable
• Hamiltonian decompositions of Cayley graphs on Abelian groups
• Hamiltonian decomposition of Cayley graphs of orders \(p^2\) and \(pq\)
• Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups
• Hamiltonian decompositions of Cayley graphs on abelian groups of odd order
• A note on Hamiltonian decompositions of Cayley graphs
• 2-spanning cyclability problems of some generalized Petersen graphs
• Hamilton decompositions of one-ended Cayley graphs
• Vertex-transitive graphs that have no Hamilton decomposition
• A conjecture of Norine and Thomas for abelian Cayley graphs
• Disjoint cycles in hypercubes with prescribed vertices in each cycle
• Hamiltonian decompositions of 6-degree Cayley graphs on commutative groups of even order
• Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups
• Orthogonal projection and liftings of Hamilton-decomposable Cayley graphs on abelian groups
• Hamilton decompositions of 6-regular Cayley graphs on even abelian groups with involution-free connections sets
• scientific article; zbMATH DE number 568807 (Why is no real title available?)
• On Hamilton decompositions of infinite circulant graphs
• A survey on Hamiltonicity in Cayley graphs and digraphs on different groups
• Vertex‐Transitive Graphs of Prime‐Squared Order Are Hamilton‐Decomposable
• Hamiltonian decompositions of 4‐regular Cayley graphs of infinite abelian groups
• Edge-disjoint Hamilton cycles in the McKay-Miller-Širáň graphs
• 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
• The Hamilton spaces of Cayley graphs on abelian groups
• Some problems on Cayley graphs

This page was built for publication: Hamiltonian decompositions of Cayley graphs on abelian groups of even order

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