Mutually Independent Hamiltonian Cycles in k-ary n-cubes when k is odd

被引:0
作者
Kao, Shin-Shin [1 ]
Wang, Pi-Hsiang [1 ]
机构
[1] Chung Yuan Christian Univ, Dept Appl Math, 200 Jong Bei Rd, Chungli, Taiwan
来源
PROCEEDINGS OF THE AMERICAN CONFERENCE ON APPLIED MATHEMATICS: RECENT ADVANCES IN APPLIED MATHEMATICS | 2009年
关键词
k-ary n-cubes; hamiltonian cycle; mutually independent; hypercubes; HYPERCUBES; GRAPHS;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The k-ary n-cubes, CA, is one of the most well-known interconnection networks in parallel computers. Let n >= 1 be an integer and k >= 3 be an odd integer. It has been shown that any Q(n)(k) is a 2n-regular, vertex symmetric and edge symmetric graph with a hamiltonian cycle. In this article, we prove that any k-ary n-cube contains 2n mutually independent hamiltonian cycles. More specifically, let v(i) is an element of V(Q(n)(k)) for 0 <= i <= vertical bar Q(n)(k)vertical bar - 1 and let < v(0),v(i),...,v(vertical bar Qnk vertical bar-1), v0 > be a hamiltonian cycle of Q(n)(k). We prove that Q(n)(k) contains 2n hamiltonian cycles of the form < v(0), v(1)(l) ,..., v(vertical bar Qnk vertical bar)(l)-1; v(0)> for 0 <= 1 <= 2n - 1, where v(i)(l) not equal v(i)(l)' whenever l not equal l'. The result is optimal since each vertex of Q(n)(k) has exactly 2n neighbors.
引用
收藏
页码:116 / +
页数:2
相关论文
共 14 条
[1]  
Bondy J.A., 1980, Graph Theory with Applications
[2]   Perfect matchings extend to Hamilton cycles in hypercubes [J].
Fink, Jiri .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (06) :1074-1076
[3]   A SURVEY OF THE THEORY OF HYPERCUBE GRAPHS [J].
HARARY, F ;
HAYES, JP ;
WU, HJ .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1988, 15 (04) :277-289
[4]   Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges [J].
Hsieh, Sun-Yuan ;
Yu, Pei-Yu .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2007, 13 (02) :153-162
[5]   Strongly Hamiltonian laceability of the even k-ary n-cube [J].
Huang, Chien-Hung .
COMPUTERS & ELECTRICAL ENGINEERING, 2009, 35 (05) :659-663
[6]   Disjoint cycles and spanning graphs of hypercubes [J].
Kobeissi, M ;
Mollard, M .
DISCRETE MATHEMATICS, 2004, 288 (1-3) :73-87
[7]  
Leighton F. T., 1992, INTRO PARALLEL ALGOR
[8]   Mutually independent hamiltonian cycles for the pancake graphs and the star graphs [J].
Lin, Cheng-Kuan ;
Tan, Jimmy J. M. ;
Huang, Hua-Min ;
Hsu, D. Frank ;
Hsu, Lih-Hsing .
DISCRETE MATHEMATICS, 2009, 309 (17) :5474-5483
[9]   Mutually independent hamiltonian paths in star networks [J].
Lin, CK ;
Huang, HM ;
Hsu, LH ;
Bau, S .
NETWORKS, 2005, 46 (02) :110-117
[10]   On k-ary n-cubes:: theory and applications [J].
Mao, WZ ;
Nicol, DM .
DISCRETE APPLIED MATHEMATICS, 2003, 129 (01) :171-193