Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/103668
Title: On a class of Hamiltonian laceable 3-regular graphs
Authors: Alspach, B.
Chen, C.C. 
McAvaney, K.
Issue Date: 10-May-1996
Source: 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
URI: http://scholarbank.nus.edu.sg/handle/10635/103668
ISSN: 0012365X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

28
checked on Feb 15, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.