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
Share
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)
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.1007/s10817-016-9396-y
Combining SAT Solvers with Computer Algebra Systems to Verify Combinatorial Conjectures
Edward Zulkoski (2016)
Gray Codes Avoiding Matchings
D. Dimitrov (2009)
10.1002/jgt.20128
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)
10.1016/0095-8956(73)90059-2
Smallest maximal matchings in the graph of the d-dimensional cube
R. Forcade (1973)
10.1007/s00373-015-1533-6
Small Matchings Extend to Hamiltonian Cycles in Hypercubes
F. Wang (2016)
10.1007/s00493-017-3731-8
Matchings Extend into 2-Factors in Hypercubes
J. Fink (2019)
10.1016/j.tcs.2017.01.010
Generalized Gray codes with prescribed ends
T. Dvorák (2017)
The Art in Computer Programming
A. Hunt (2001)
10.21136/cpm.1984.108506
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)
10.1137/S0895480103432805
Hamiltonian Cycles with Prescribed Edges in Hypercubes
T. Dvořák (2005)
10.1137/0406012
Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn
F. Ruskey (1993)
10.1016/j.disc.2013.12.014
Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
F. Wang (2014)
10.1112/PLMS/PDW004
Proof of the middle levels conjecture
T. Mütze (2016)
10.1137/080732687
Matching Extendability in Hypercubes
J. Vandenbussche (2009)
10.1007/s00453-013-9750-y
Rounds in Combinatorial Search
G. Wiener (2013)
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.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