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 -