Frustração de Arestas em (3, 6)-Fullerenes
Resumo
Grafos (3, 6)-fullerenes são grafos planares, 3-conexos, cúbicos cujas faces têm tamanho 3 ou 6. Determinar o menor número de arestas a serem deletadas de um grafo de modo a obter um subgrafo gerador bipartido é conhecido na literatura [Doslic and Vukicevic 2007] como o Problema de Frustração de Arestas. Neste trabalho, abordamos o Problemas da Frustração de Arestas em grafos (3, 6)- fullerenes. Mostramos que todo grafo (3, 6)-fullerene com n vértices torna-se bipartido após a retirada de no máximo q4 3n arestas.
Referências
Bondy, J. A. and Murty, U. S. R. (2008). Graph theory. Macmillan/Elsevier, Canada.
Dosli´c, T. and Vukicevi´c, D. (2007). Computing the bipartite edge frustration of fullerene graphs. Discrete Applied Mathematics, 155(10):1294–1301.
Klein, S., Faria, L., and Stehl´ık, M. (2012). Odd cycle transversals and independent sets in fullerene graphs. SIAM Journal of Discrete Mathematic, 48(3):1458–469.
Dosli´c, T. and Vukicevi´c, D. (2007). Computing the bipartite edge frustration of fullerene graphs. Discrete Applied Mathematics, 155(10):1294–1301.
Klein, S., Faria, L., and Stehl´ık, M. (2012). Odd cycle transversals and independent sets in fullerene graphs. SIAM Journal of Discrete Mathematic, 48(3):1458–469.
Publicado
04/07/2016
Como Citar
NICODEMOS, Diego S.; KLEIN, Sulamita; FARIA, Luerbio.
Frustração de Arestas em (3, 6)-Fullerenes. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 784-787.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9765.
