Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
394332 | Information Sciences | 2010 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Petr Gregor, Riste Å krekovski,