Online citations, reference lists, and bibliographies.

Gray Codes Extending Quadratic Matchings

T. Dvorák, J. Fink
Published 2019 · Mathematics, Computer Science

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