Ciclos e Caminhos Longos em Grafos Ímpares
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≥3 e uma conjectura atribuída a Lovász implica que Ok tem um caminho hamiltoniano para k≥1. 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.Referências
Biggs, N. (1979). Some odd graph theory. Ann. New York Acad. Sci., 319:71–81.
Bueno, L. R., Faria, L., Figueiredo, C. M. H., and Fonseca, G. D. (2009). Hamiltonian paths in odd graphs. Appl. Anal. Discrete Math., 3(2):386–394.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York.
Gilbert, E. N. (1958). Gray codes and paths on the n-cube. Bell Systems Tech. J., 37:815– 826.
Gray, F. (1953). Pulse code communication. U.S. Patent 2632058.
Havel, I. (1983). Semipaths in directed cubes. In Fiedler, M., editor, Graphs and other Combinatorial Topics, pages 101–108, Teubner, Leipzig. Teubner-Texte Math.
Johnson, J. R. (2004). Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A, 105(2):255–271.
Karp, R. M. (1972). Reducibility among combinatorial problems. In Miller, R. and Thatcher, J., editors, Complexity of Computer Computations, pages 85–103, New York. Plenum Press.
Lovász, L. (1970). Problem 11. In Combinatorial Structures and their Applications. Gordon and Breach.
Savage, C. D. and Winkler, P. (1995). Monotone gray codes and the middle levels problem. J. Combin. Theory Ser. A, 70(2):230–248.
Shields, I. and Savage, C. D. (2004). A note on hamilton cycles in Kneser graphs. Bulletin of the Institute for Combinatorics and Its Applications, 40:13–22.
Bueno, L. R., Faria, L., Figueiredo, C. M. H., and Fonseca, G. D. (2009). Hamiltonian paths in odd graphs. Appl. Anal. Discrete Math., 3(2):386–394.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York.
Gilbert, E. N. (1958). Gray codes and paths on the n-cube. Bell Systems Tech. J., 37:815– 826.
Gray, F. (1953). Pulse code communication. U.S. Patent 2632058.
Havel, I. (1983). Semipaths in directed cubes. In Fiedler, M., editor, Graphs and other Combinatorial Topics, pages 101–108, Teubner, Leipzig. Teubner-Texte Math.
Johnson, J. R. (2004). Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A, 105(2):255–271.
Karp, R. M. (1972). Reducibility among combinatorial problems. In Miller, R. and Thatcher, J., editors, Complexity of Computer Computations, pages 85–103, New York. Plenum Press.
Lovász, L. (1970). Problem 11. In Combinatorial Structures and their Applications. Gordon and Breach.
Savage, C. D. and Winkler, P. (1995). Monotone gray codes and the middle levels problem. J. Combin. Theory Ser. A, 70(2):230–248.
Shields, I. and Savage, C. D. (2004). A note on hamilton cycles in Kneser graphs. Bulletin of the Institute for Combinatorics and Its Applications, 40:13–22.
Publicado
23/07/2013
Como Citar
MESQUITA, Felipe de Campos ; BUENO, Letícia Rodrigues.
Ciclos e Caminhos Longos em Grafos Ímpares. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 32. , 2013, Maceió.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 152-160.
