Perfect matchings extend to Hamilton cycles in hypercubes

被引：56

作者：

Fink, Jiri ^{[1
]}

机构：

[1] Charles Univ Prague, Fac Math & Phys, Dept Appl Math, George Town 11800, Malaysia

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2007年 / 97卷 / 06期

关键词：

hypercube; Hamiltonian cycle; perfect matching;

D O I：

10.1016/j.jctb.2007.02.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Kreweras' conjecture [G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87-91] asserts that any perfect matching of the hypercube Q(d), d >= 2, can be extended to a Hamilton cycle. We prove this conjecture. (C) 2007 Elsevier Inc. All rights reserved.

引用

页码：1074 / 1076

页数：3