Online citations, reference lists, and bibliographies.
Referencing for people who value simplicity, privacy, and speed.
Get Citationsy
← Back to Search

Gray Codes Extending Quadratic Matchings

Tomás Dvorák, Jirí Fink
Published 2019 · Mathematics, Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
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.
Get Citationsy
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
This paper references
Hamilton Cycles Which Extend Transposition Matchings in Cayley Graphs of S N
F. Ruskey (1993)
Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
T. Dvorák (2008)
Matching graphs of hypercubes and complete bipartite graphs
J. Fink (2009)
Combining SAT Solvers with Computer Algebra Systems to Verify Combinatorial Conjectures
Edward Zulkoski (2016)
Gray Codes Avoiding Matchings
D. Dimitrov (2009)
Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
R. Caha (2006)
The Art of Computer Programming: Combinatorial Algorithms, Part 1
D. Knuth (2011)
Smallest maximal matchings in the graph of the d-dimensional cube
R. Forcade (1973)
Small Matchings Extend to Hamiltonian Cycles in Hypercubes
F. Wang (2016)
Matchings Extend into 2-Factors in Hypercubes
J. Fink (2019)
Generalized Gray codes with prescribed ends
T. Dvorák (2017)
The Art in Computer Programming
A. Hunt (2001)
On Hamiltonian circuits and spanning trees of hypercubes
I. Havel (1984)
Matchings of quadratic size extend to long cycles in hypercubes
T. Dvorák (2016)
Proof of themiddle levels conjecture
T. Mütze (2016)
Hamiltonian Cycles with Prescribed Edges in Hypercubes
T. Dvořák (2005)
Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn
F. Ruskey (1993)
Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
F. Wang (2014)
Proof of the middle levels conjecture
T. Mütze (2016)
Matching Extendability in Hypercubes
J. Vandenbussche (2009)
Rounds in Combinatorial Search
G. Wiener (2013)
Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes
P. Gregor (2009)
Perfect matchings extend to Hamilton cycles in hypercubes
J. Fink (2007)
Edge Multiplicity and Other Trace Functions
G. Wiener (2007)
Extending a perfect matching to a Hamiltonian cycle
A. Alahmadi (2015)

This paper is referenced by
Semantic Scholar Logo Some data provided by SemanticScholar