Ciclos e Caminhos Longos em Grafos Ímpares

Abstract

O grafo ímpar Ok é o grafo cujos vértices são todos os subconjuntos de tamanho k de um conjunto com (2k+1) elementos e dois vértices são adjacentes se eles são disjuntos. Uma conjectura atribuída a Biggs afirma que o grafo Ok é hamiltoniano para k > 4 e uma conjectura atribuída a Lovász implica que Ok tem um caminho hamiltoniano para k > 2. A partir de um ciclo hamiltoniano em Ok-1, mostramos como construir um ciclo em Ok com pelo menos 75% dos vértices de Ok. Adicionalmente, nós provamos que, para todo k, o grafo ímpar tem um caminho com pelo menos 50% dos vértices de Ok.