Article ID Journal Published Year Pages File Type
394332 Information Sciences 2010 10 Pages PDF
Abstract
Let Gnk be the subgraph of the hypercube Qn induced by levels between k and n-k, where n⩾2k+1 is odd. The well-known middle-level conjecture asserts that G2k+1k is Hamiltonian for all k⩾1. We study this problem in Gnk for fixed k. It is known that Gn0 and Gn1 are Hamiltonian for all odd n⩾3. In this paper we prove that also Gn2 is Hamiltonian for all odd n⩾5, and we conjecture that Gnk is Hamiltonian for every k⩾0 and every odd n⩾2k+1.
Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
, ,