Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes |
| |
Authors: | Petr Gregor |
| |
Affiliation: | Department of Theoretical Computer Science and Mathematical Logic, Charles University, Malostranské nám. 25, 118 00 Prague, Czech Republic |
| |
Abstract: | Recently, Fink [J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007) 1074-1076] affirmatively answered Kreweras’ conjecture asserting that every perfect matching of the hypercube extends to a Hamiltonian cycle. We strengthen this result in the following way. Given a partition of the hypercube into subcubes of nonzero dimensions, we show for every perfect matching of the hypercube that it extends on these subcubes to a Hamiltonian cycle if and only if it interconnects them. |
| |
Keywords: | Hypercube Hamiltonian cycle Perfect matching Subcube |
本文献已被 ScienceDirect 等数据库收录! |
|