Matchings Extend to Hamiltonian Cycles in 5-Cube

Discussiones Mathematicae Graph Theory

Zhao Weisheng¹  Wang Fan² 

[1] Institute for Interdisciplinary Research, Jianghan University, Wuhan, Hubei 430056, P.R. China;School of Sciences, Nanchang University, Nanchang, Jiangxi 330000, P.R. China;

关键词: hypercube;    hamiltonian cycle;    matching;    05c38;    05c45;   

DOI  :  10.7151/dmgt.2010

来源: DOAJ

【 摘 要 】

Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ∈ {2, 3, 4}. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.

【 授权许可】

Unknown