Towards a problem of Ruskey and Savage on matching extendability

DOI10.1016/j.endm.2017.06.071zbMath1378.05115OpenAlexW2742731641MaRDI QIDQ1689953

Petr Gregor, Jiří Fink, Tomáš Novotný, Tomáš Dvořák

Publication date: 18 January 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2017.06.071

zbMATH Keywords

hypercubematchingHamiltonian cycleRuskey and Savage problem

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Uses Software

• Hypothesis-checker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extensions to 2-factors in bipartite graphs
• Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes
• Matching graphs of hypercubes and complete bipartite graphs
• Perfect matchings extend to Hamilton cycles in hypercubes
• Smallest maximal matchings in the graph of the d-dimensional cube
• Proof of the middle levels conjecture
• Matching Extendability in Hypercubes
• A constant-time algorithm for middle levels Gray codes
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Small matchings extend to Hamiltonian cycles in hypercubes

This page was built for publication: Towards a problem of Ruskey and Savage on matching extendability