On hamiltonian cycles in the prism over the odd graphs |
| |
| Authors: | Letícia R Bueno Peter Horák |
| |
| Institution: | 1. Coppe—Universidade Federal Do Rio De Janeiro, Brazil;2. IAS, University of Washington, Tacoma |
| |
| Abstract: | The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph Ok is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that Ok is hamiltonian for all k>2. We show that the prism over Ok is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011 |
| |
| Keywords: | Hamiltonian cycle prism over a graph Kneser graphs |
|
|
