| |
| The anti-Kekul'{e} numberof a connected graph $G$ is the smallest number of edges to be removed to create a connected subgraph without perfect matchings. In this article, weshow that the anti-Kekul'{e} number of a 2-connectedcubic graph is either 3 or 4, and the anti-Kekul'{e} numberof a connected cubic bipartite graph is always equal to 4.Direct application of these results shows that the anti-Kekul'{e} number of aboron-nitrogen fullerene, a toroidal fullerene and a Klein-bottle fullerene is 4, and the anti-Kekul'{e}number of a (3,6)-fullerene is 3. Moreover, we show that all the smallest anti-Kekul'{e} sets in a cubic graph can be found out in a polynomial time with respect to the order of the graph. |
|
| Keywords:Graph Theory, anti-Kelul'{e} set, anti-Kelul'{e} number, cubic graph, boron-nitrogen fullerene, $(3,6)$-fullerene. |
|
