Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes
Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes
复制标题
DOI：
10.1016/j.disc.2008.02.013
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
Petr Gregor
中科院分区：
文献类型：
--
作者：
Petr Gregor
最近，Fink [J. Fink，Perfect matching extend to汉密尔顿cycles in hypercubes，J. Combin. Theory Ser. B 97（2007）1074-1076]肯定地回答了Kreweras的猜想，该猜想断言超立方体的每个完美匹配都延伸到Hamilton圈。我们以下列方式加强这一结果。给定一个分区的超立方体的非零维的子立方体，我们表明，每一个完美的匹配的超立方体，它扩展到这些子立方体的一个哈密尔顿循环，当且仅当它互连它们。
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.