## Abstract

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.

Original language | English |
---|---|

Article number | 1030 |

Journal | Art of Discrete and Applied Mathematics |

Volume | 2 |

Issue number | 1 |

Early online date | 12 Aug 2018 |

DOIs | |

Publication status | Published - Jan 2019 |

## Scopus Subject Areas

- Applied Mathematics
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## User-Defined Keywords

- Anti-Kekulé number
- Anti-Kekulé set
- Cubic graphs