On the anti-Kekulé problem of cubic graphs

An edge set S of a connected graph G is called an anti-Kekulé set if G− S is connected and has no perfect matchings, where G − S denotes the subgraph obtained by deleting all edges in S from G. The anti-Kekulé number of a graph G, denoted by ak(G), is the cardinality of a smallest anti-Kekulé set of G. It is NP-complete to determine the anti-Kekulé number of a graph. In this paper, we show that the anti-Kekulé number of a 2-connected cubic graph is either 3 or 4, and the anti-Kekulé number of a connected cubic bipartite graph is always equal to 4. Furthermore, a polynomial time algorithm is given to find all smallest anti-Kekulé sets of a connected cubic graph.