Hamiltonian Cycles in Kneser Graphs for

Autor: Candido F. X. de Mendonça, Celina M. H. de Figueiredo, Luerbio Faria, Letícia Rodrigues Bueno, Rodrigo de A. Hausen
Rok vydání: 2011
Předmět:
Zdroj: Electronic Notes in Discrete Mathematics. 37:291-296
ISSN: 1571-0653
DOI: 10.1016/j.endm.2011.05.050
Popis: The Kneser graph K ( n , k ) has all k-subsets of an n-set as its vertices and two subsets are adjacent if they are disjoint. Lovasz conjectured that every connected vertex-transitive graph has a hamiltonian path. For n ⩾ 2 k + 1 , the Kneser graphs form a well-studied family of connected, regular, vertex-transitive graphs. A direct computation of hamiltonian cycles in K ( n , k ) is not feasible for large values of k, because K ( n , k ) has ( n k ) vertices. We give a sufficient condition for K ( 2 k + 2 , k ) to be hamiltonian for odd k: the existence of a particular hamiltonian path in a reduced graph over K ( 2 k + 2 , k ) . Also, we extend this result to the bipartite Kneser graphs B ( 2 k + 2 , k ) for odd k.
Databáze: OpenAIRE