Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges  

作　　者：Xie-Bin CHEN 

机构地区：[1]College of Mathematics and Statistics, Minnan Normal University, Zhangzhou 363000, China

出　　处：《Frontiers of Mathematics in China》2014年第1期17-30,共14页中国高等学校学术文摘·数学（英文）

基　　金：Acknowledgements The author would like to thank the anonymous referees for their valuable suggestions. This work was supported by the Natural Science Foundation of Fujian Province （No. 2011J01025）.

摘　　要：The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.

关 键 词：Hamiltonian cycle FAULT-TOLERANCE 3-ary n-cube linear forest interconnection network 

分 类 号：O157.5[理学—数学] TP393[理学—基础数学]