Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

2013/01/14 by Fan Wang, Heping Zhang, Wang, Fan +1
Mathematics · #05C38 #05C45 #05C70 #68M10 #68M15 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #math.CO #math.OC #msc:05C38 #msc:05C45 #msc:05C70 #msc:68M10 #msc:68M15 #msc:68R10

paper · pdf · doi:10.48550/arxiv.1301.2931

16 pages, 10 figures

arxiv created 2013/01/14 · arxiv updated 2013/01/15

Abstract

Ruskey and Savage asked the following question: Does every matching of Q_n for n≥2 extend to a Hamiltonian cycle of Q_n? J. Fink showed that the question is true for every perfect matching, and solved the Kreweras' conjecture. In this paper we consider the question in hypercubes with faulty edges. We show that every matching M of at most 2n-1 edges can be extended to a Hamiltonian cycle of Q_n for n≥2. Moreover, we can prove that when n≥4 and M is nonempty this result still holds even if Q_n has at most n-1-\lceil(|M|)/(2)\rceil faulty edges with one exception.

Related

• Matchings in Hypercubes Extend to Long Cycles
• Matchings in hypercubes extend to long cycles
• Hamiltonian cycles passing through matchings in k-ary n-cubes
• A perfect matching reciprocity method for embedding multiple hypercubes in an augmented cube: Applications to Hamiltonian decomposition and fault-tolerant Hamiltonicity
• Hamiltonian paths extending a set of matchings in hypercubes