On a class of Hamiltonian laceable 3-regular graphs

✍ Scribed by Brian Alspach; C.C. Chen; Kevin McAvaney

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 741 KB
• Volume: 151
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00077-v

✦ Synopsis

Using the concept of brick-products, Alspach and Zhang showed in that all cubic Cayley graphs over dihedral groups are Hamiltonian. It is also conjectured that all brick-products C(2n, m, r) are Hamiltonian laceable, in the sense that any two vertices at odd distance apart can be joined by a Hamiltonian path. In this paper, we shall study the Hamiltonian iaceability of brick-products C(2n, m, r) with only one cycle (i.e. m = 1). To be more specific, we shall provide a technique with which we can show that when the chord length r is 3,5,7 or 9, the corresponding brick-products are Hamiltonian laceable. Let s = gcd((r + 1)/2, n) and t = gcd((r -1)/2, n). We then show that the brick-product C(2n, 1, r) is Hamiltonian laceable if (i) st is even; (ii) s is odd and rs = r + 1 + 3s (mod 4n); or (iii) t is odd and rt = r -1 -3t (mod 4n). In general, when n is sufficiently large, say n >/r 2 -r + 1, then the brick-product is also Hamiltonian iaceable.