On the anti-Kekulé problem of cubic graphs

  • Qiuli Li Lanzhou University, China
  • Wai Chee Shiu Hong Kong Baptist University, Hong Kong
  • Pak Kiu Sun Hong Kong Baptist University, Hong Kong
  • Dong Ye Middle Tennessee State University, United States
Keywords: Anti-Kekulé set, anti-Kekulé number, cubic graphs

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.

Published
2018-08-12
Section
Articles