✦ LIBER ✦

Pseudo-cartesian product and hamiltonian decompositions of Cayley graphs on abelian groups

✍ Scribed by Cong Fan; Don R. Lick; Jiuqiang Liu

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 971 KB
Volume: 158
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00035-u

No coin nor oath required. For personal study only.

✦ 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 we generalize a result by Kotzig that the Cartesian product of any two cycles can be decomposed into two hamiltonian cycles and show that any pseudo-Cartesian product of two cycles can be decomposed into two hamiltonian cycles. By applying that result we first give an alternative proof for the main result in including the missing cases, and then we show that the conjecture is true for most 6-regular connected Cayley graphs on abelian groups of odd order and for some 6-regular connected Cayley graphs on abelian groups of even order.

It is known that any connected Cayley graph on a finite abelian group is hamiltonian [lo]. In 1984, Alspach [l] conjectured that any 2k-regular connected Cayley

📜 SIMILAR VOLUMES

Hamiltonian decompositions of Cayley gra

Hamiltonian decompositions of Cayley graphs on Abelian groups

✍ Jiuqiang Liu 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 606 KB

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= {sl,sz, s3} is a minimal generating set of A with 1 Al odd, or S={sl,s& . . . . sk} is a genera

Hamiltonian Decompositions of Cayley Gra

Hamiltonian Decompositions of Cayley Graphs on Abelian Groups of Odd Order

✍ Jiuqiang Liu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 380 KB

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

Connected Cayley graphs of semi-direct p

Connected Cayley graphs of semi-direct products of cyclic groups of prime order by abelian groups are hamiltonian

✍ Erich Durnberger 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 705 KB

In this paper it is shown that every connected Cayley graph of a semt-direct product of a cyclic group of prime order by an abelian group is hamiltonian. In particular, every connected Cayley graph of a group G is hamiltonian provided that G is of order greater than 2 and it contains a normal cyclic

Hamilton cycle and Hamilton path extenda

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

✍ Štefko MiklaviČ; Primož Šparl 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is __n__‐__HC‐extendable__ if it contains a path of length __n__ and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is __weakly n__‐__HP‐