Article ID Journal Published Year Pages File Type
4647263 Discrete Mathematics 2014 16 Pages PDF
Abstract

Alspach conjectured that every connected Cayley graph on a finite Abelian group AA is Hamilton-decomposable. Liu has shown that for |A||A| even, if S={s1,…,sk}⊂AS={s1,…,sk}⊂A is an inverse-free strongly minimal generating set of AA, then the Cayley graph Cay(A;S⋆)(A;S⋆), is decomposable into kk Hamilton cycles, where S⋆S⋆ denotes the inverse-closure of SS. Extending these techniques and restricting to the 66-regular case, this article relaxes the constraint of strong minimality on SS to require only that SS be strongly aa-minimal, for some a∈Sa∈S and the index of 〈a〉〈a〉 be at least four. Strong aa-minimality means that 2s∉〈a〉2s∉〈a〉 for all s∈S∖{a,−a}s∈S∖{a,−a}. Some infinite families of open cases for the 6-regular Cayley graphs on even order Abelian groups are resolved. In particular, if |s1|≥|s2|>2|s3||s1|≥|s2|>2|s3|, then Cay(A;{s1,s2,s3}⋆)Cay(A;{s1,s2,s3}⋆) is Hamilton-decomposable.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,