Hamiltonian decompositions of Cayley graphs on abelian groups of even order (Q1400966)

From MaRDI portal





scientific article; zbMATH DE number 1965036
Language Label Description Also known as
English
Hamiltonian decompositions of Cayley graphs on abelian groups of even order
scientific article; zbMATH DE number 1965036

    Statements

    Hamiltonian decompositions of Cayley graphs on abelian groups of even order (English)
    0 references
    0 references
    17 August 2003
    0 references
    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.
    0 references
    Hamiltonian decomposition
    0 references
    Cayley graph
    0 references
    abelian group
    0 references

    Identifiers