Resultados de aproximação de hamiltonicidade em grafos kneser

O grafo Kneser K(n,k) e o grafo cujos vertices sao os subconjuntos com k elementos de um conjunto {1,...,n} e dois vertices sao unidos por uma aresta se o par correspondente subconjuntos e disjunto. Uma conjectura de Biggs afirma que O k = K(2k+1,k) e hamiltoniano para k>2 e uma conjectura de Lovasz implica que todo grafo Kneser conexo tem um caminho hamiltoniano. Neste trabalho, mostramos que o prisma sobre todo grafo Kneser conexo e sobre seu grafo bipartido duplo e hamiltoniano.