On the anti-Kelul\'{e} problem of cubic graphs

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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-11
Main Authors: Li, Qiuli, Wai Chee Shiu, Sun, Pak Kiu, Ye, Dong
Format: Article
Language:English
Subjects:
Algorithms
Graph algorithms
Graph theory
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 find the smallest anti-Kekulé set of a graph. In this paper, we show that the anti-Kekul\'{e} number of a 2-connected cubic graph is either 3 or 4, and the anti-Kekul\'{e} 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\'{e} sets of a connected cubic graph.
ISSN:2331-8422