RESEARCH ARTICLE

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

  • Xie-Bin CHEN
Expand
  • College of Mathematics and Statistics, Minnan Normal University, Zhangzhou 363000, China

Received date: 10 Mar 2012

Accepted date: 23 Oct 2012

Published date: 01 Feb 2014

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

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 E0 (≠Ø) be a linear forest and F (≠Ø) be a set of faulty edges in Qn3 such that E0F = Øand |E0| + |F|≤2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn3-F,and the upper bound 2n-2 is sharp.

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]. Frontiers of Mathematics in China, 2014 , 9(1) : 17 -30 . DOI: 10.1007/s11464-013-0344-4

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

3
Chen X B. On path bipancyclicity of hypercubes. Inform Process Lett, 2009, 109: 594-598

DOI

4
Chen X B. Hamitonian paths and cycles passing through a prescribed path in hypercubes. Inform Process Lett, 2009, 110: 77-82

DOI

5
Chen X B. Cycles passing through a prescribed path in a hypercube with faulty edges. Inform Process Lett, 2010, 110: 625-629

DOI

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

7
Dvořák T. Hamiltonian cycles with prescribed edges in hypercubes. SIAM J Discrete Math, 2005, 19: 135-144

DOI

8
Dvořák T, Greror P. Hamiltonian paths with prescribed edges in hypercubes. Discrete Math, 2007, 307: 1982-1998

DOI

9
Fan J, Jia X. Edge-pancyclicity and path-embeddability of bijective connection graphs. Inform Sci, 2008, 178: 340-351

DOI

10
Fan J, Jia X, Lin X. Embedding of cycles in twisted cubes with edge-pancyclic. Algorithmica, 2008, 51: 264-282

DOI

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

12
Hsieh S Y, Lin T J. Panconnectivity and edge-pancyclicity of k-ary n-cube. Networks, 2009, 54: 1-11

DOI

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

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

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

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

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

18
Stewart I A, Xiang Y, Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Trans Parall Distrib Sys, 2009, 20: 25-33

DOI

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

20
Tsai C H. Fault-free cycles passing through prescribed paths in hypercubes with faulty edges. Appl Math Lett, 2009, 22: 852-855

DOI

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

22
Wang S, Lin S. Path embeddings in faulty 3-ary n-cubes. Inform Sci, 2010, 180: 191-197

DOI

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

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

25
Xu J M, Ma M. A survey on path and cycle embedding in some networks. Front Math China, 2009, 4: 217-252

DOI

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

Options
Outlines

/