Hamiltonicity of hypercubes with a constraint of required and faulty edges

被引:5
作者
Hsu, Lih-Hsing
Liu, Shu-Chung [1 ]
Yeh, Yeong-Nan
机构
[1] China Univ Technol, Gen Educ Ctr, Hsinchu, Taiwan
[2] Providence Univ, Dept Comp & Informat Engn, Taichung, Taiwan
[3] Acad Sinica, Inst Math, Taipei 115, Taiwan
关键词
Hamiltonian cycles and paths; edge-fault-tolerance; required edge; hypercubes;
D O I
10.1007/s10878-007-9059-3
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Let R and F be two disjoint edge sets in an n-dimensional hypercube Q(n) . We give two constructing methods to build a Hamiltonian cycle or path that includes all the edges of R but excludes all of F. Besides, considering every vertex of Q(n) incident to at most n - 2 edges of F, we show that a Hamiltonian cycle exists if (A) vertical bar R vertical bar + 2 vertical bar F vertical bar <= 2n - 3 when vertical bar R vertical bar >= 2, or (B) vertical bar R vertical bar + 2 vertical bar F vertical bar <= 4n - 9 when vertical bar R vertical bar <= 1. Both bounds are tight. The analogous property for Hamiltonian paths is also given.
引用
收藏
页码:197 / 204
页数:8
相关论文
共 7 条
[1]  
HAGGKVIST R, 1979, GRAPH THEORY RELATED, P219
[2]  
HSU LH, 2001, 2 PAC RIM C MATH TAI
[3]  
Kronk H.V., 1969, The Many Facets of Graph Theory, P193
[4]  
LATIFI S, 1992, FTCS-22 : THE TWENTY-SECOND INTERNATIONAL SYMPOSIUM ON FAULT-TOLERANT COMPUTING, P178
[5]   On ring embedding in hypercubes with faulty nodes and links [J].
Sengupta, A .
INFORMATION PROCESSING LETTERS, 1998, 68 (04) :207-214
[6]  
Simmons G. J., 1978, C NUMER, V21, P649
[7]   Embedding a ring in a hypercube with both faulty links and faulty nodes [J].
Tseng, YC .
INFORMATION PROCESSING LETTERS, 1996, 59 (04) :217-222