Referencing for people who value simplicity, privacy, and speed.Get Citationsy
← Back to Search
Gray Codes Extending Quadratic Matchings
Published 2019 · Mathematics, Computer Science
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Funding information Research supported by the Czech Science Foundation under grant GA14-10799S. The second author was also supported by Charles University project UNCE/SCI/004. Is it true that every matching in the n-dimensional hypercube Qn can be extended to a Gray code? More than two decades have passed since Ruskey and Savage asked this question and the problem still remains open. A solution is known only in some special cases, including perfect matchings or matchings of linear size. This paper shows that the answer to the Ruskey-Savage problem is affirmative for every matching of size at most n2 16 + n 4 . The proof is based on an inductive construction which extends balanced matchings in the completion of the hypercube K (Qn ) by edges of Qn into a Hamilton cycle of K (Qn ). On the other hand, we show that for every n ≥ 9 there is a balanced matching in