On the Anti-Kekulé Number of a Hexagonal System

摘要

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-Kekulé set of H is a set S of edges of H such that H - S is a connected graph that has no Kekulé structures. The minimum of cardinalities of anti-Kekulé sets of H is called the anti-Kekulé number of H, denoted as ak(H). An anti-Kekulé set S of H is called a smallest anti-Kekulé set of H if the cardinality of S equals ak(H). It is obvious that a single hexagon has no anti-Kekulé 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 Kekulé 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-Kekulé set in a normal hexagonal system, where n is the number of its vertices.