首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号