×

Extending a perfect matching to a Hamiltonian cycle. (English) Zbl 1311.05157

Summary: F. Ruskey and C. Savage [SIAM J. Discrete Math. 6, No. 1, 152–166 (1993; Zbl 0771.05050)] conjectured that in the \(d\)-dimensional hypercube, every matching \(M\) can be extended to a Hamiltonian cycle. J. Fink [J. Comb. Theory, Ser. B 97, No. 6, 1074–1076 (2007; Zbl 1126.05080)] verified this for every perfect matching \(M\), remarkably even if \(M\) contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of the cubes: for every \(d \geq 7\) and every \(k\), where \(7 \leq k \leq 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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: Link