A Note on the Middle Levels Conjecture

Details A Note on the Middle Levels Conjecture A Note on the Middle Levels Conjecture

2009-12-23

arxiv.org/abs/0912.4564v2

Computer Science

Discrete Mathematics

10 pages, 7 figures; Note on the results of k=19 is added at the end of the paper

Scientific paper

The middle levels conjecture asserts that there is a Hamiltonian cycle in the middle two levels of $2k+1$-dimensional hypercube. The conjecture is known to be true for $k \leq 17$ [I.Shields, B.J.Shields and C.D.Savage, Disc. Math., 309, 5271--5277 (2009)]. In this note, we verify that the conjecture is also true for $k=18$ by constructing a Hamiltonian cycle in the middle two levels of 37-dimensional hypercube with the aid of the computer. We achieve this by introducing a new decomposition technique and an efficient algorithm for ordering the Narayana objects.

Affiliated with

Also associated with

No associations

Rating

A Note on the Middle Levels Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Note on the Middle Levels Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on the Middle Levels Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-362682