On a class of Hamiltonian laceable 3-regular graphs

被引:22
作者
Alspach, B
Chen, CC
McAvaney, K
机构
[1] SIMON FRASER UNIV, DEPT MATH & STAT, BURNABY, BC V5A 1S6, CANADA
[2] NATL UNIV SINGAPORE, DEPT MATH, SINGAPORE 117548, SINGAPORE
[3] DEAKIN UNIV, DEPT COMP & MATH, GEELONG, VIC 3217, AUSTRALIA
关键词
D O I
10.1016/0012-365X(94)00077-V
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 equivalent to 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 greater than or equal to r(2) - r + 1, then the brick-product is also Hamiltonian laceable.
引用
收藏
页码:19 / 38
页数:20
相关论文
共 3 条
[1]  
ALSPACH B, 1989, ARS COMBINATORIA, V28, P101
[2]  
ALSPACH B, 1991, 468 LEE KONG CHAIN C
[3]  
CHEN CC, 1981, LECT NOTES MATH, V884, P23