Please use this identifier to cite or link to this item:
|Title:||On a class of Hamiltonian laceable 3-regular graphs|
|Citation:||Alspach, B.,Chen, C.C.,McAvaney, K. (1996-05-10). On a class of Hamiltonian laceable 3-regular graphs. Discrete Mathematics 151 (1-3) : 19-38. ScholarBank@NUS Repository.|
|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.|
|Source Title:||Discrete Mathematics|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 25, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.