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
Share
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
10.1007/s10817-016-9396-y
Combining SAT Solvers with Computer Algebra Systems to Verify Combinatorial Conjectures
Edward Zulkoski (2016)
Gray Codes Avoiding Matchings
Darko Dimitrov (2009)
10.1137/060678476
Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
T. Dvorák (2008)
10.1016/j.ejc.2009.03.007
Matching graphs of hypercubes and complete bipartite graphs
J. Fink (2009)
10.1137/0406012
Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn
F. Ruskey (1993)
10.1137/S0895480103432805
Hamiltonian Cycles with Prescribed Edges in Hypercubes
T. Dvořák (2005)
10.1016/j.disc.2008.02.013
Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes
P. Gregor (2009)
10.1016/j.jctb.2007.02.007
Perfect matchings extend to Hamilton cycles in hypercubes
J. Fink (2007)
10.1002/jgt.20128
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)
10.1112/PLMS/PDW004
Proof of the middle levels conjecture
Torsten Mütze (2016)
10.1016/j.disc.2013.12.014
Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
Fan Wang (2014)
10.1007/s00453-013-9750-y
Rounds in Combinatorial Search
Gábor Wiener (2013)
10.1137/080732687
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)
10.21136/cpm.1984.108506
On Hamiltonian circuits and spanning trees of hypercubes
I. Havel (1984)
10.1016/j.tcs.2017.01.010
Generalized Gray codes with prescribed ends
Tomás Dvorák (2017)
10.1007/s00493-017-3731-8
Matchings Extend into 2-Factors in Hypercubes
Jirí Fink (2019)
10.1007/s00373-015-1533-6
Small Matchings Extend to Hamiltonian Cycles in Hypercubes
Fan Wang (2016)
10.1016/0095-8956(73)90059-2
Smallest maximal matchings in the graph of the d-dimensional cube
R. Forcade (1973)
10.1016/j.endm.2007.07.076
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