Extending a perfect matching to a Hamiltonian cycle

Adel Alahmadi, Robert E. L. Aldred, Ahmad Alkenani, Rola Hijazi, P. Solé, Carsten Thomassen

Research output: Contribution to journalJournal articleResearchpeer-review

892 Downloads (Pure)

Abstract

In 1993 Ruskey and Savage conjectured that in the d-dimensional hypercube, every matching M can be extended to a Hamiltonian cycle. Fink verified this for every perfect matchingM, remarkably even ifM contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of the cubes: for every d ≥ 7 and every k, where 7 ≥ k ≥ d, the d-dimensional hypercube contains a k-regular spanning subgraph such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle. We do not know if this result can be extended to k = 4; 5; 6. It cannot be extended to k = 3. Indeed, there are only three 3-regular graphs such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle, namely the complete graph on 4 vertices, the complete bipartite 3-regular graph on 6 vertices and the 3-cube on 8 vertices. Also, we do not know if there are graphs of girth at least 5 with this matching-extendability property.
Original languageEnglish
JournalDiscrete Mathematics and Theoretical Computer Science (Online Edition)
Volume17
Issue number1
Pages (from-to)241-254
ISSN1365-8050
Publication statusPublished - 2015

Keywords

  • COMPUTER
  • MATHEMATICS,
  • MATHEMATICS
  • HYPERCUBES
  • EDGES
  • some well classifying words

Fingerprint Dive into the research topics of 'Extending a perfect matching to a Hamiltonian cycle'. Together they form a unique fingerprint.

Cite this