Ciclos e Caminhos Longos em Grafos Ímpares

Felipe de Campos Mesquita, Letícia Rodrigues Bueno

Resumo


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.

Palavras-chave


Ciclos hamiltonianos; Caminhos hamiltonianos; Grafos Ímpares

Texto completo:

PDF


A REIC mudou de endereço! Para acessar as edições publicadas e/ou submeter seu artigo, acesse https://sol.sbc.org.br/journals/index.php/reic.