On the anti-Kekulé problem of cubic graphs

Qiuli Li, Wai Chee SHIU*, Pak Kiu SUN, Dong Ye

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)


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 languageEnglish
Article number1030
JournalArt of Discrete and Applied Mathematics
Issue number1
Early online date12 Aug 2018
Publication statusPublished - 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


Dive into the research topics of 'On the anti-Kekulé problem of cubic graphs'. Together they form a unique fingerprint.

Cite this