Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419124 | Discrete Applied Mathematics | 2007 | 8 Pages |
Abstract
Bipartite edge frustration of a graph is defined as the smallest number of edges that have to be deleted from the graph to obtain a bipartite spanning subgraph. We show that for fullerene graphs this quantity can be computed in polynomial time and obtain explicit formulas for the icosahedral fullerenes. We also report some computational results and discuss a potential application of this invariant in the context of fullerene stability.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tomislav Došlić, Damir Vukičević,