Matchings Extend to Hamiltonian Cycles in 5-Cube

• Autorzy: Fan Wang , Weisheng Zhao
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hypercube; Hamiltonian cycle; matching

Kategorie tematyczne

• 05C45: Eulerian and Hamiltonian graphs
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 38
• Numer: 1
• Strony: 217-231

Daty

wydano

2018-02-01

otrzymano

2016-09-27

poprawiono

2016-11-04

zaakceptowano

2016-11-04

online

2017-12-30

Twórcy

autor

Fan Wang

• , , , Jiangxi , P.R.

autor

Weisheng Zhao

• , , , Hubei , P.R.

Identyfikatory

DOI

10.7151/dmgt.2010