Search

An edge set $S$ of a connected graph $G$ is called an anti-Kekul\'e 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\'e number of a graph $G$, denoted by $ak(G)$, is the cardinality of a smallest anti-Kekul\'e set of $G$. It is NP-complete to find the smallest anti-Kekul\'e 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., Comment: 14 pages, 3 figures

Two inequalities bridging the three isolated graph invariants, incidence chromatic number, star arboricity and domination number, were established. Consequently, we deduced an upper bound and a lower bound of the incidence chromatic number for all graphs. Using these bounds, we further reduced the upper bound of the incidence chromatic number of planar graphs and showed that cubic graphs with orders not divisible by four are not 4-incidence colorable. The incidence chromatic numbers of Cartesian product, join and union of graphs were also determined., 8 pages