A Linear-Time Algorithm for Computing the Complete Forcing Number and the Clar Number of Catacondensed Hexagonal Systems

摘要

Let G be a graph with edge set E(G) that admits a perfect matching M. A forcing set of M is a subset of M contained in no other perfect matching of G. A complete forcing set of G, recently introduced by Xu et al. [Complete forcing numbers of catacondensed hexagonal systems, J. Comb. Optim., doi: 10.1007/s10878-013-9624-x] is a subset of E(G) to which the restriction of any perfect matching M is a forcing set of M. The minimum possible cardinality of a complete forcing set of G is the complete forcing number of G. In this article, we prove theorems for general graphs about explicit relations between the complete forcing numbers under the operation of identifying edges. Regarding its applications to a catacondensed hexagonal system, we prove an unexpectedly linear relationship between the complete forcing number and the Clar number, an important concept on Clar's aromatic sextet theory in chemistry, propose a linear-time algorithm for computing the complete forcing number and the Clar number and, finally, give an exponential sharp lower bound on the number of minimum complete forcing sets.