Matchings extend to Hamiltonian cycles in hypercubes with faulty edges

Abstract

We consider the problem of existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cube {{\displaystyle Q}}_n, and obtain the following results. Let n\ge \mathrm{3},\hspace{0.17em}M\subset E({{\displaystyle Q}}_n), and F\subset E({{\displaystyle Q}}_n)\backslash M with \mathrm{1}\le \left|F\right|\le \mathrm{2}n-\mathrm{4}-\left|M\right|. If M is a matching and every vertex is incident with at least two edges in the graph {{\displaystyle Q}}_n-F, then all edges of M lie on a Hamiltonian cycle in {{\displaystyle Q}}_n-F. Moreover, if \left|M\right|=\mathrm{1} or \left|M\right|=\mathrm{2}, then the upper bound of number of faulty edges tolerated is sharp. Our results generalize the well-known result for \left|M\right|=\mathrm{1}.

Keywords

Hypercube / Hamiltonian cycle / fault tolerance / matching / inter-connection network

References

[1] Bondy J A, Murty U S R. Graph Theory. New York: Springer, 2007

[2] Caha R, Koubek V. Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets. J Graph Theory, 2006, 51: 137–169

[3] Chen X-B. Cycles passing through prescribed edges in a hypercube with some faulty edges. Inform Process Lett, 2007, 104: 211–215

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

[5] Chen X-B. The 2-path-bipanconnectivity of hypercubes. Inform Sci, 2013, 239: 283–293

[6] Chen X-B. Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges. Front Math China, 2014, 9: 17–30

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

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

[9] Fink J. Perfect matchings extend to Hamiltonian cycles in hypercubes. J Combin Theory Ser B 2007, 97: 1074–1076

[10] Li T K, Tsai C H, Tan J J M, Hsu L H. Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes. Inform Process Lett, 2003, 87: 107–110

[11] Stewart T A. Hamiltonian cycles through prescribed edges in k-ary n-cubes. In: Combinatorial Optimization and Applications. Lecture Notes in Comput Sci, Vol 6831. 2011, 82–97

[12] Tsai C H. Linear array and ring embeddings in conditional faulty hypercubes. Theoret Comput Sci, 2004, 314: 431–443

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

[14] Wang F, Sun W. Perfect matchings extended to two or more Hamiltonian cycles in hypercubes. Discrete Math, 2019, 342: 505–510

[15] Wang F, Zhang H. Prescribed matchings extended to Hamiltonian cycles in hypercubes with faulty edges. Discrete Math, 2014, 321: 35–44

[16] Wang F, Zhang H. Matchings extend to Hamiltonian cycles in k-ary n-cubes. Inform Sci, 2015, 305: 1–13

[17] 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

[18] Wang S, Li J, Wang R. Hamiltonian cycles passing through linear forests in k-ary n-cubes. Discrete Appl Math, 2011, 159: 1425–1435

[19] 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

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

[21] Yang Y, Li J, Wang S. Embedding fault-free Hamiltonian paths with prescribed linear forests into faulty ternary n-cubes. Theoret Comput Sci, 2019, 767: 1–15

[22] Yang Y, Wang S. Fault-free Hamiltonian cycles passing through a linear forest in ternary n-cubes with faulty edges. Theoret Comput Sci, 2013, 491: 78{82

[23] Zhang S, Zhang X. Fault-free Hamiltonian cycles passing through prescribed edges in k-ary n-cubes with faulty edges. IEEE Trans Parallel Distrib Syst, 2015, 26: 434–443

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature