On the anti-Kekulé number and odd cycle transversal of regular graphs

Let GG be a graph with a perfect matching. The anti-Kekulé number is the smallest number of edges of GG whose removal will result in a connected subgraph with no perfect matching. In this note, we show that, if GG is a cyclically (r+1)(r+1)-edge-connected rr-regular graph (r≥3r≥3) of even order, then either the anti-Kekulé number of GG is at least r+1r+1, or GG is not bipartite, and the smallest odd cycle transversal of GG has at most rr edges. For cubic graphs, the bound of the anti-Kekulé number is optimal. Our result generalizes previous results on anti-Kekulé numbers of fullerenes obtained by Kutnar et al. [K. Kutnar, J. Sedlar, D. Vukičević, On the anti-Kekulé number of leapfrog fullerenes, J. Math. Chem. 45 (2009) 431–441.] and Yang et al. [Q. Yang, D. Ye, H. Zhang, Y. Lin, On the anti-Kekulé number of fullerenes, MATCH Commun. Math. Comput. Chem. 67 (2) (2012) 281–288].