On a class of Hamiltonian laceable 3-regular graphs

Abstract

Using the concept of brick-products, Alspach and Zhang showed in Alspach and Zhang (1989) 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 laceability 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 ≥ r2 - r + 1, then the brick-product is also Hamiltonian laceable.