Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
classification
🧮 math.CO
math.OC
keywords
edgeseveryfaultyhamiltonianmatchingquestioncycleextend
read the original abstract
Ruskey and Savage asked the following question: Does every matching of $Q_{n}$ for $n\geq2$ 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\geq2$. Moreover, we can prove that when $n\geq4$ and $M$ is nonempty this result still holds even if $Q_{n}$ has at most $n-1-\lceil\frac{|M|}{2}\rceil$ faulty edges with one exception.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.