Hamiltonian Cycles in Kneser Graphs
Resumo
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 values 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 most twice.
Referências
Biggs, N. (1979). Some odd graph theory. Ann. New York Acad. Sci., 319:71–81.
Bueno, L. R. (2009). Ciclos Hamiltonianos em Grafos Kneser. PhD dissertation, Univ. Federal do Rio de Janeiro.
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.
Bueno, L. R. and Horák, P. (2009). On hamiltonian cycles in the prism over the odd graphs. J. Graph Theory (submitted).
Chen, Y.-C. (2003). Triangle-free hamiltonian Kneser graphs. J. Combin. Theory Ser. B, 89(1):1–16.
Duffus, D. A., Kierstead, H. A., and Snevily, H. S. (1994). An explicit 1-factorization in the middle of the boolean lattice. Journal of Combinatorial Theory, Series A, 65:334–342.
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.
Garey, M. R., Johnson, D. S., and Tarjan, R. E. (1976). The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5:704–714.
Havel, I. (1983). Semipaths in directed cubes. In Fiedler, M., editor, Graphs and other Combinatorial Topics, pages 101–108, Teubner, Leipzig. Teubner-Texte Math.
Horák, P., Kaiser, T., Rosenfeld, M., and Ryjáček, Z. (2005). The prism over the middle-levels graph is hamiltonian. Order, 22(1):73–81.
Jackson, B. and Wormald, N. C. (1990). k-walks of graphs. Austral. J. Combin., 2:135–146.
Johnson, J. R. (2004). Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A, 105(2):255–271.
Johnson, J. R. and Kierstead, H. A. (2004). Explicit 2-factorisations of the odd graph. Order, 21:19–27.
Kaiser, T., Ryjáček, Z., Král, D., Rosenfeld, M., and Voss, H.-J. (2007). Hamilton cycles in prisms. Journal of Graph Theory, 56:249–269.
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.
Kierstead, H. A. and Trotter, W. T. (1988). Explicit matchings in the middle two levels of the boolean algebra. Order, 5:163–171.
Krishnamoorthy, M. S. (1975). An np-hard problem in bipartite graphs. SIGACT News, 7(1):26.
Lovász, L. (1970). Problem 11. In Combinatorial Structures and their Applications. Gordon and Breach.
Papadimitriou, C. H. and Steiglitz, K. (1976). Some complexity results for the traveling salesman problem. In Proc. 8th Ann. ACM Symp. on Theory of Computing, pages 1–9, New York. Association for Computing Machinery.
Paulraja, P. (1993). A characterization of hamiltonian prisms. Journal of Graph Theory, 17:161–171.
Savage, C. D. and Winkler, P. (1995). Monotone gray codes and the middle levels problem. Journal Combinatorial Theory Series A, 70(2):230–248.
Shields, I. and Savage, C. D. (1999). A Hamilton path heuristic with applications to the middle two levels problem. In Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), volume 140, pages 161–178.
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.
Shields, I., Shields, B. J., and Savage, C. D. (2009). An update on the middle levels problem. Discrete Mathematics, 309(17):5271–5277.
Bueno, L. R. (2009). Ciclos Hamiltonianos em Grafos Kneser. PhD dissertation, Univ. Federal do Rio de Janeiro.
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.
Bueno, L. R. and Horák, P. (2009). On hamiltonian cycles in the prism over the odd graphs. J. Graph Theory (submitted).
Chen, Y.-C. (2003). Triangle-free hamiltonian Kneser graphs. J. Combin. Theory Ser. B, 89(1):1–16.
Duffus, D. A., Kierstead, H. A., and Snevily, H. S. (1994). An explicit 1-factorization in the middle of the boolean lattice. Journal of Combinatorial Theory, Series A, 65:334–342.
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.
Garey, M. R., Johnson, D. S., and Tarjan, R. E. (1976). The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5:704–714.
Havel, I. (1983). Semipaths in directed cubes. In Fiedler, M., editor, Graphs and other Combinatorial Topics, pages 101–108, Teubner, Leipzig. Teubner-Texte Math.
Horák, P., Kaiser, T., Rosenfeld, M., and Ryjáček, Z. (2005). The prism over the middle-levels graph is hamiltonian. Order, 22(1):73–81.
Jackson, B. and Wormald, N. C. (1990). k-walks of graphs. Austral. J. Combin., 2:135–146.
Johnson, J. R. (2004). Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A, 105(2):255–271.
Johnson, J. R. and Kierstead, H. A. (2004). Explicit 2-factorisations of the odd graph. Order, 21:19–27.
Kaiser, T., Ryjáček, Z., Král, D., Rosenfeld, M., and Voss, H.-J. (2007). Hamilton cycles in prisms. Journal of Graph Theory, 56:249–269.
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.
Kierstead, H. A. and Trotter, W. T. (1988). Explicit matchings in the middle two levels of the boolean algebra. Order, 5:163–171.
Krishnamoorthy, M. S. (1975). An np-hard problem in bipartite graphs. SIGACT News, 7(1):26.
Lovász, L. (1970). Problem 11. In Combinatorial Structures and their Applications. Gordon and Breach.
Papadimitriou, C. H. and Steiglitz, K. (1976). Some complexity results for the traveling salesman problem. In Proc. 8th Ann. ACM Symp. on Theory of Computing, pages 1–9, New York. Association for Computing Machinery.
Paulraja, P. (1993). A characterization of hamiltonian prisms. Journal of Graph Theory, 17:161–171.
Savage, C. D. and Winkler, P. (1995). Monotone gray codes and the middle levels problem. Journal Combinatorial Theory Series A, 70(2):230–248.
Shields, I. and Savage, C. D. (1999). A Hamilton path heuristic with applications to the middle two levels problem. In Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), volume 140, pages 161–178.
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.
Shields, I., Shields, B. J., and Savage, C. D. (2009). An update on the middle levels problem. Discrete Mathematics, 309(17):5271–5277.
Publicado
20/07/2010
Como Citar
BUENO, Letícia Rodrigues.
Hamiltonian Cycles in Kneser Graphs. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 23. , 2010, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 113-120.
ISSN 2763-8820.
