On the Anti-Kekule Number of a Hexagonal System
Jinzhuan Cai, Zhang, HP (reprint author), Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China., Zhang, HP (reprint author), Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China. · Lanzhou University Institutional Repository · 2013
A hexagonal system is a connected plane graph without cut vertices in which each interior face is a regular hexagon. Let H be a hexagonal system. An anti-Kekule set of H is a set S of edges of H such that H - S is a connected graph that has no Kekule structures. The minimum of cardinalities of anti-Kekule sets of H is called the anti-Kekule number of H, denoted as ak(H). An anti-Kekule set S of H is called a smallest anti-Kekule set of H if the cardinality of S equals ak(H). It is obvious that a single hexagon has no anti-Kekule sets. In this paper, we show that for a hexagonal system H with more than one hexagon, ak(H) = 0 if and only if H has no Kekule structures, ak(H) = 1 if and only if H has a fixed double edge, and ak(H) is either 2 or 3 for the other cases. Further by applying perfect path systems we give a characterization whether ak(H) = 2 or 3, and present an O(n(2)) algorithm for finding a smallest anti-Kekule set in a normal hexagonal system, where n is the number of its vertices.