Ciclos e Caminhos Longos em Grafos Ímpares - Mesquita, Felipe de Campos; Bueno, Letícia Rodrigues (Anais do Concurso de Trabalhos de Iniciação Científica da SBC (CTIC-SBC); 2013: Anais do XXXII Concurso de Trabalhos de Iniciação Científica da SBC, 2013)
O grafo ímpar O k é 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 O k é hamiltoniano para k≥3 e uma conjectura atribuída a Lovász implica que O k tem um caminho hamiltoniano para k≥1. A partir de um ciclo hamiltoniano em O k-1 , mostramos como construir um ciclo em O k com pelo menos 75% dos vértices de O k . Adicionalmente, nós provamos que, para todo k, o grafo ímpar tem um caminho com pelo menos 50% dos vértices de O k .