TY - JOUR

T1 - On the anti-Kekulé problem of cubic graphs

AU - Li, Qiuli

AU - Shiu, Wai Chee

AU - Sun, Pak Kiu

AU - Ye, Dong

N1 - Funding Information:
∗This work is supported by NSFC (grant nos. 11401279 and 11371180), the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20130211120008), the Fundamental Research Funds for the Central Universities (no. lzujbky-2017-28), and General Research Fund of Hong Kong. †The corresponding author. E-mail addresses: [email protected] (Qiuli Li), [email protected] (Wai Chee Shiu), [email protected] (Pak Kiu Sun), [email protected] (Dong Ye)

PY - 2019/1

Y1 - 2019/1

N2 - 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.

AB - 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.

KW - Anti-Kekulé number

KW - Anti-Kekulé set

KW - Cubic graphs

UR - http://www.scopus.com/inward/record.url?scp=85079901023&partnerID=8YFLogxK

U2 - 10.26493/2590-9770.1264.94b

DO - 10.26493/2590-9770.1264.94b

M3 - Journal article

AN - SCOPUS:85079901023

SN - 2590-9770

VL - 2

JO - Art of Discrete and Applied Mathematics

JF - Art of Discrete and Applied Mathematics

IS - 1

M1 - 1030

ER -