Frustração de Arestas em (3, 6)-Fullerenes

  • Diego S. Nicodemos UFRJ
  • Sulamita Klein UFRJ
  • Luerbio Faria UERJ

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.
Publicado
04/07/2016
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.