Frustração de Arestas em (3, 6)-Fullerenes
Abstract
A (3, 6)-fullerene graph is a cubic bridgeless plane graph with all faces of size 3 or 6. Determining the smallest number of edges that have to be deleted from the graph to obtain a bipartite spanning subgraph is known in the literature [Doslic and Vukicevic 2007] as the Bipartite Edge Frustration Problem. In this paper, we investigate the Bipartite Edge Frustration Problem in (3, 6)-fullerene graphs. We show that every graph (3, 6)-fullerene on n vertices becomes bipartite after deleting at mostq 4 3n edges.
References
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.
Published
2016-07-04
How to Cite
NICODEMOS, Diego S.; KLEIN, Sulamita; FARIA, Luerbio.
Frustração de Arestas em (3, 6)-Fullerenes. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
