Embedding Three Edge-Disjoint Hamiltonian Cycles into Locally Twisted Cubes

被引:2
作者
Pai, Kung-jui [1 ]
机构
[1] Ming Chi Univ Technol, Dept Ind Engn & Management, New Taipei, Taiwan
来源
COMPUTING AND COMBINATORICS (COCOON 2021) | 2021年 / 13025卷
关键词
Edge-disjoint hamiltonian cycles; Locally twisted cubes; Interconnection networks;
D O I
10.1007/978-3-030-89543-3_31
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The n-dimensional locally twisted cube LTQ(n), a variation of the hypercube Q(n), has the same number of vertices and the same number of edges as Q(n), but it has only about half of the diameter of Q(n). The existence of the Hamiltonian cycle provides an advantage when implementing algorithms that require a ring structure. In addition, k (>= 2) edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity for the interconnection network. Hung [Theoretical Computer Science 412, 4747-4753, 2011] proved that LTQ(n) with n >= 4 contains two edge-disjoint Hamiltonian cycles, and posted an open problem what is the maximum number of edge-disjoint Hamiltonian cycles in LTQ(n) for n >= 6? In this paper, we show that there exist three edge-disjoint Hamiltonian cycles on LTQ(n) while n >= 6.
引用
收藏
页码:367 / 374
页数:8
相关论文
共 20 条
[1]   Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes [J].
Bae, MM ;
Bose, B .
IEEE TRANSACTIONS ON COMPUTERS, 2003, 52 (10) :1271-1284
[2]   2 EDGE-DISJOINT HAMILTONIAN CYCLES IN THE BUTTERFLY GRAPH [J].
BARTH, D ;
RASPAUD, A .
INFORMATION PROCESSING LETTERS, 1994, 51 (04) :175-179
[3]   Constructing edge-disjoint spanning trees in locally twisted cubes [J].
Hsieh, Sun-Yuan ;
Tu, Chang-Jen .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (8-10) :926-932
[5]  
Hung RW, 2012, LECT NOTES ENG COMP, P362
[7]  
Kung-jui Pai, 2020, Algorithmic Aspects in Information and Management. 14th International Conference, AAIM 2020. Proceedings. Lecture Notes in Computer Science (LNCS 12290), P448, DOI 10.1007/978-3-030-57602-8_40
[8]   INTERLEAVED ALL-TO-ALL RELIABLE BROADCAST ON MESHES AND HYPERCUBES [J].
LEE, SG ;
SHIN, KG .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (05) :449-458
[9]   Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes [J].
Lin, Jia-Cian ;
Yang, Jinn-Shyong ;
Hsu, Chiun-Chieh ;
Chang, Jou-Ming .
INFORMATION PROCESSING LETTERS, 2010, 110 (10) :414-419
[10]   Embedding Cycles and Paths in Product Networks and Their Applications to Multiprocessor Systems [J].
Lin, Tsong-Jie ;
Hsieh, Sun-Yuan ;
Juan, Justie Su-Tzu .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2012, 23 (06) :1081-1089