Ciclos Hamiltonianos em Grafos Kneser
Autores
|
4455 |
1998,414,257,1996
|
|
|
4456 |
1998,414,257,1996
|
|
|
4457 |
1998,414,257,1996
|
|
|
4458 |
Peter Horák
(Co-orientador) |
1998,414,257,1996
|
Informações:
Publicações do PESC
O grafo Kneser K(n,k) tem como seu conjunto de vértices todos os subconjuntos de tamanho k de um conjunto de n elementos e dois destes subconjuntos são adjacentes se eles são disjuntos. O grafo ímpar Ok é o caso especial do grafo Kneser quando n=2k+1. Uma conjectura aberta de Lovász afirma que Ok tem um caminho hamiltoniano para todo k>=1. Até agora, a conjectura de Lovász foi comprovada em Ok para k<=13. Nós melhoramos estes valores mostrando que Ok tem um caminho hamiltoniano para 14<=k<=17. Fazemos isso sem executar quaisquer algoritmos. Ao invés disso, utilizamos resultados existentes para o problema de encontrar um ciclo hamiltoniano no grafo Bk: o grafo dos níveis médios do (2k+1)-cubo; assim relacionando estes dois importantes problemas. Por fim, estabelecemos quão próximos os grafos ímpares estão de ser hamiltonianos segundo uma interpretação bem definida de "próximo''. Mostramos que, para todo k par, Ok tem um passeio gerador fechado no qual todo vértice aparece no máximo duas vezes. Além disso, mostramos que para todo k ímpar, Ok tem uma trilha geradora fechada na qual cada vértice aparece no máximo duas vezes.
The Kneser graph K(n,k) is a graph whose vertices are all subsets with k elements of a set that has n elements, and two vertices are joined by an edge if the corresponding pair of k-subsets is disjoint. The odd graph Ok is the special case of the Kneser graph when n=2k+1. A long standing conjecture due to Lovász claims that Ok has a hamiltonian path for all k>=1. Previously, Lovász's conjecture has been proved for k<=13. We have improved these values by showing that Ok has a hamiltonian path for 14<=k<=17. Our proofs do not use the execution of algorithms, relying instead upon existing results on the problem of finding a hamiltonian cycle in the graph Bk - the middle levels graph of the (2k+1)-cube - thus relating these two important problems. At last, we have established how close the odd graphs are to being hamiltonian, according to a well-defined interpretation of "close''. We have shown that, for every k even, Ok has a closed spanning walk in which every vertex appears at most twice. Moreover, for every k odd, we have shown that Ok has a closed spanning trail in which every vertex appears at most twice.