Hamiltonian Decompositions of Cayley Graphs on Abelian Groups of Odd Order

✍ Scribed by Jiuqiang Liu

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 380 KB
• Volume: 66
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.0007

✦ Synopsis

Alspach has conjectured that any 2k-regular connected Cayley graph cay(A, S) on a finite abelian group A can be decomposed into k hamiltonian cycles. In this paper, the conjecture is shown to be true if S=[s 1 , s 2 , ..., s k ] is a minimal generating set of an abelian group A of odd order (where a generating set S of a group G is minimal if no proper subset of S can generate G ). 1996 Academic Press, Inc.

1. Introduction Let (A, +) be a finite group and S be a subset of A with 0 not in S. The Cayley graph cay(A, S) is defined to be the graph G with V(G)=A and E(G )=[xy | x, y # A, x&y # S or y&x # S]. We say an edge xy in cay(A, S ) is generated by s # S if x&y=s or y&x=s and the subgraph Q of cay(A, S) is generated by s if E(Q) consists of all the edges generated by s.

Remark 1. From the definition, it is clear that any element of S with order 2 generates a 1-factor of cay(A, S ) while any element of S with order at least 3 generates a 2-factor of cay(A, S ). Furthermore, cay(A, S ) is connected if and only if S generates A.

It is known that any connected Cayley graph on a finite abelian group is hamiltonian . In , Alspach conjectured that any 2k-regular connected Cayley graph on a finite abelian group has a hamiltonian decomposition. Bermond, Favaron, and Maheo [4] proved that every 4-regular connected Cayley graph cay(A, S) on a finite abelian group A can be decomposed into two hamiltonian cycles. Liu showed that the conjecture is true provided that either cay(A, S ) is 2m-regular and S=[s 1 , s 2 , ..., s k ] is a generating set of A such that gcd(ord(s i ), ord(s j ))=1 for i{j or S= [s 1 , s 2 , s 3 ] is a minimal generating set of A with |A| being odd. Here our main purpose is to prove the following theorem which establishes the conjecture for a more general case.

article no.