Autores

4823
1996,257,414,1998
4824
1996,257,414,1998
4825
1996,257,414,1998
4826
Peter Horák
(Co-orientador)
1996,257,414,1998

Informações:

Publicações do PESC

Título
Hamiltonian Cycles in Kneser Graphs
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Artigo em Congresso
Número de registro
Data
7/2010
Resumo
O grafo Kneser K(n, k) é o grafo cujos vértices são todos os subconjuntos com k elementos de um conjunto que tem n elementos e dois vértices são unidos por uma aresta se o par correspondente de conjuntos de tamanho k é disjunto. O grafo ímpar Ok é o caso especial do grafo Kneser quando n=2k + 1. Uma conjectura de Lovász afirma que Ok tem um caminho hamiltoniano para k ≥ 1. Anteriormente, a conjectura de Lovász tinha sido provada para todo k ≤ 13. Nós melhoramos estes valores mostrando que Ok tem um caminho hamiltoniano para 14 ≤ k ≤ 17. Adicionalmente, estabelecemos quão próximos os grafos ímpares estão de serem hamiltonianos: Ok tem um passeio gerador fechado ou uma trilha geradora fechada no qual cada vértice aparece duas vezes no máximo.
Abstract
The Kneser graph K(n, k) is the graph whose vertices are all the 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-sets 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 k ≥ 1. Previously, Lovász’s conjecture had been proved for all k ≤ 13. We have improved these avalues by showing that Ok has a hamiltonian path for 14 ≤ k ≤ 17. Additionally, we have established how close the odd graphs are to being hamiltonian: Ok has a closed spanning walk or trail in which every vertex appears at mosttwice.
Topo