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

doi:10.1007/s11464-013-0344-4

Front Math Chin

2014, Vol. 9

Issue (1) : 17-30 https://doi.org/10.1007/s11464-013-0344-4

RESEARCH ARTICLE

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

Xie-Bin CHEN(

)

College of Mathematics and Statistics, Minnan Normal University, Zhangzhou 363000, China

Download: PDF(145 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

The k-ary n-cube Qnk (n≥2 and k≥3) is one of the most popular interconnection networks. In this paper, we consider the problem of a faultfree Hamiltonian cycle passing through a prescribed linear forest (i.e., pairwise vertex-disjoint paths) in the 3-ary n-cube Qn3 with faulty edges. The following result is obtained. Let E₀ (≠?) be a linear forest and F (≠?) be a set of faulty edges in Qn3 such that E₀ ∩ F = ?and |E₀| + |F|≤2n - 2. Then all edges of E₀ lie on a Hamiltonian cycle in Qn3-F,and the upper bound 2n-2 is sharp.

Keywords Hamiltonian cycle fault-tolerance 3-ary n-cube linear forest interconnection network

Corresponding Author(s): CHEN Xie-Bin,Email:chenxbfz@163.com

Issue Date: 01 February 2014

Cite this article:

Xie-Bin CHEN. Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges[J]. Front Math Chin, 2014, 9(1): 17-30.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-013-0344-4
https://academic.hep.com.cn/fmc/EN/Y2014/V9/I1/17

1	Bondy J A, Murty U S R. Graph Theory. New York: Springer, 2007
2	Chen X B. Cycles passing through prescribed edges in a hypercube with some faulty edges. Inform Process Lett , 2007, 104: 211-215 doi: 10.1016/j.ipl.2007.06.014
3	Chen X B. On path bipancyclicity of hypercubes. Inform Process Lett , 2009, 109: 594-598 doi: 10.1016/j.ipl.2009.02.009
4	Chen X B. Hamitonian paths and cycles passing through a prescribed path in hypercubes. Inform Process Lett , 2009, 110: 77-82 doi: 10.1016/j.ipl.2009.10.010
5	Chen X B. Cycles passing through a prescribed path in a hypercube with faulty edges. Inform Process Lett , 2010, 110: 625-629 doi: 10.1016/j.ipl.2010.05.015
6	Dong Q, Yang X, Wang D. Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links. Inform Sci , 2010, 180: 198-208 doi: 10.1016/j.ins.2009.09.002
7	Dvo?ák T. Hamiltonian cycles with prescribed edges in hypercubes. SIAM J Discrete Math , 2005, 19: 135-144 doi: 10.1137/S0895480103432805
8	Dvo?ák T, Greror P. Hamiltonian paths with prescribed edges in hypercubes. Discrete Math , 2007, 307: 1982-1998 doi: 10.1016/j.disc.2005.12.045
9	Fan J, Jia X. Edge-pancyclicity and path-embeddability of bijective connection graphs. Inform Sci , 2008, 178: 340-351 doi: 10.1016/j.ins.2007.08.012
10	Fan J, Jia X, Lin X. Embedding of cycles in twisted cubes with edge-pancyclic. Algorithmica , 2008, 51: 264-282 doi: 10.1007/s00453-007-9024-7
11	Fan J, Lin X, Jia X, Lau R W H. Edge-pancyclicity of twisted cubes. Lecture Notes in Computer Sciences , 2005, 3827: 1090-1099 doi: 10.1007/11602613_108
12	Hsieh S Y, Lin T J. Panconnectivity and edge-pancyclicity of k-ary n-cube. Networks , 2009, 54: 1-11 doi: 10.1002/net.20290
13	Hsieh S Y, Lin T J, Huang H L. Panconnectivity and edge-pancyclicity of 3-ary n-cubes. J Supercomputing , 2007, 42: 225-233 doi: 10.1007/s11227-007-0133-5
14	Li J, Wang S, Liu D. Pancyclicity of ternary n-cube networks under the conditional fault model. Inform Process Lett , 2011, 111: 370-374 doi: 10.1016/j.ipl.2011.01.009
15	Li J, Wang S, Liu D, Lin S. Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges. Inform Sci , 2011, 181: 2260-2267 doi: 10.1016/j.ins.2011.01.027
16	Lin S, Wang S, Li C. Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements. Discrete Appl Math , 2011, 159: 212-223 doi: 10.1016/j.dam.2010.10.015
17	Stewart I A, Xiang Y. Embedding long paths in k-ary n-cubes with faulty nodes and links. IEEE Trans Parall Distrib Sys , 2008, 19: 1071-1085 doi: 10.1109/TPDS.2007.70787
18	Stewart I A, Xiang Y, Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Trans Parall Distrib Sys , 2009, 20: 25-33 doi: 10.1109/TPDS.2008.45
19	Teng Y H, Tan J J M, Tsay C W, Hsu L H. The paths embedding of the arrangement graphs with prescribed vertices in given position. J Combin Optim , 2012, 24: 627-646 doi: 10.1007/s10878-011-9418-y
20	Tsai C H. Fault-free cycles passing through prescribed paths in hypercubes with faulty edges. Appl Math Lett , 2009, 22: 852-855 doi: 10.1016/j.aml.2008.08.021
21	Wang S, Li J, Wang R. Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cubes. Inform Sci , 2011, 181: 3054-3065 doi: 10.1016/j.ins.2011.03.011
22	Wang S, Lin S. Path embeddings in faulty 3-ary n-cubes. Inform Sci , 2010, 180: 191-197 doi: 10.1016/j.ins.2009.09.007
23	Wang W Q, Chen X B. A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges. Inform Process Lett , 2008, 107: 205-210 doi: 10.1016/j.ipl.2008.02.016
24	Xiang Y, Stewart I A. Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption. IEEE Trans Parall Distrib Sys , 2011, 22: 1506-1513 doi: 10.1109/TPDS.2011.22
25	Xu J M, Ma M. A survey on path and cycle embedding in some networks. Front Math China , 2009, 4: 217-252 doi: 10.1007/s11464-009-0017-5
26	Yang M C, Tan J J M, Hsu L H. Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes. J Parall Distrib Computing , 2007, 67: 362-368 doi: 10.1016/j.jpdc.2005.10.004

[1]	Xie-Bin CHEN. Matchings extend to Hamiltonian cycles in hypercubes with faulty edges[J]. Front. Math. China, 2019, 14(6): 1117-1132.
[2]	Shiying WANG, Zhenhua WANG, Mujiangshan WANG, Weiping HAN. *g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM model**[J]. Front. Math. China, 2017, 12(5): 1221-1234.

Viewed

Full text

Abstract

Cited

Shared

Discussed