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