Resultados de Aproximação de Hamiltonicidade em Grafos Kneser
Palavras-chave:
Ciclo Hamiltoniano. Grafo Kneser.Resumo
O grafo Kneser K(n,k) é o grafo cujos vértices são os subconjuntos com k elementos de um conjunto {1,...,n} e dois vértices são unidos por uma aresta se o par correspondente subconjuntos é disjunto. Uma conjectura de Biggs afirma que Ok = K(2k+1,k) é hamiltoniano para k>2 e uma conjectura de Lovász implica que todo grafo Kneser conexo tem um caminho hamiltoniano. Neste trabalho, mostramos que o prisma sobre todo grafo Kneser conexo e sobre seu grafo bipartido dup.
Downloads
Referências
ASRATIAN, A.S.; DENLEY, T.M.J.; HÄGGKVIST, R. Bipartite graphs and their applications. Cambridge Tracts in Mathematics, v. 131, Cambridge University Press, 1998.
BABAI, L. Long cycles in vertex-transitive graphs. Journal of Graph Theory, v. 3, n. 3, p. 301-304, 1979.
BUENO, L.R.; FARIA, L.; FIGUEIREDO, C.M.H.; FONSECA, G.D. Hamiltonian paths in odd graphs, Applicable Analysis and Discrete Mathematics., v. 3, n. 2, p. 386-394, 2009.
BUENO, L.R.; HORÁK, P. On hamiltonian cycles in the prism over the odd graphs, Journal of Graph Theory, v. 68, n. 3, p. 177-188, 2011.
ČADA, R.; KAISER, T.; ROSENFELD, M.; RYJÁČEK, Z. Hamiltonian decompositions of prisms over cubic graphs, Discrete Mathematics, v. 286, n. 1-2, p. 45–56, 2004.
CHEN, Y.-C. Triangle-free hamiltonian Kneser graphs, Journal of Combinatorial Theory Series B, v. 89, n. 1, p. 1-16, 2003.
FLEISCHNER, H. The prism of a 2-connected, planar, cubic graph is hamiltonian (a proof independent of the four colour theorem), Graph theory in memory of G.A. Dirac, p. 141-170, 1988.
GAREY, M.R.; JOHNSON, D.S. Computers and Intractability, A Guide to the Theory of NPCompleteness. W.H. Freeman and Company, New York, 1979.
HAMILTON, W.R. Letter to John T. Graves on the Icosian, 17 oct., 1856. In: Halberstam, H. e Ingram, R. E. (org). The Mathematical Papers of Sir William Rowan HAMILTON. New York: Cambridge University Press, v. 3 (Algebra), 1931, p. 612-625.
HAVEL, I. Semipaths in directed cubes. Graphs and other combinatorial topics, p. 101-108, 1983.
HORÁK, P.; KAISER, T.; ROSENFELD, M.; RYJÁČEK, Z. The prism over the middle-levels graph is hamiltonian. Order, v. 22, n. 1, p. 73-81, 2005.
JOHNSON, J.R. Long cycles in the middle two layers of the discrete cube, Journal of Combinatorial Theory Series A, v. 105, n. 2, p. 255-271, 2004.
JOHNSON, J.R. An inductive construction for Hamilton cycles in Kneser graphs. The Electronic Journal of Combinatorics, v. 18, n. 1, 2011.
KAISER, T.; RYJÁČEK, Z.; KRÁL, D.; ROSENFELD, M.; VOSS, H.-J. Hamilton cycles in prisms. Journal of Graph Theory, v. 56, n. 4, p. 249-269, 2007.
KARP, R.M. Reducibility among combinatorial problems. In: Miller, R.E. e Thatcher, J.W. (org). Complexity of Computer Computations. Plenum Press, 1972, p. 85-103.
LOVÁSZ, L. Problem 11, Combinatorial structures and their applications. 1970.
LUCAS, E. Théorie des fonctions numériques simplement périodiques. American Journal of Mathematics, v. 1, n. 2, p. 184-196, 1878.
MÜTZE, T. Proof of the middle levels conjecture. ArXiv e-prints, disponível em 1404.4442, 2014.
MÜTZE, T.; SU, P. Bipartite Kneser graphs are hamiltonian. ArXiv e-prints, disponível em 1503.09175, 2015.
PAULRAJA, P. A characterization of hamiltonian prisms. Journal of Graph Theory, v. 17, n. 2, p. 161-171, 1993.
SHIELDS, I.; SAVAGE, C.D. A note on Hamilton cycles in Kneser graphs. Bulletin of the Institute for Combinatorics and Its Applications, v. 40, p. 13-22, 2004.
SHIMADA, M.; AMANO, K. A note on the middle levels conjecture. CoRR abs/0912.4564, 2011.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Revista Brasileira de Iniciação Científica
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
