Resultados de aproximação de hamiltonicidade em grafos kneser

Felipe de Campos Mesquita, Rodrigo de Alencar Hausen, Letícia Rodrigues Bueno

Resumo


 

O grafo Kneser K(n,k) é o grafo cujos vértices são os subconjuntos com k elementos de um conjunto {1,...,n} e dois vértices são unidos por uma aresta se o par correspondente subconjuntos é disjunto. Uma conjectura de Biggs afirma que Ok = K(2k+1,k) é hamiltoniano para k>2 e uma conjectura de Lovász 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 é hamiltoniano.

 

Texto completo:

116-132

Apontamentos

  • Não há apontamentos.


 

 

 

Revista Brasileira de Iniciação Científica, Itapetininga, SP, Brasil, ISSN: 2359-232X

 Licença Creative Commons Este obra está licenciado com uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional.