A linear-time algorithm for computing the complete forcing number and the clar number of catacondensed hexagonal systems

Wai Hong CHAN, Shou-Jun XU, Ge NONG

Research output: Contribution to journalArticlespeer-review

11 Citations (Scopus)

Abstract

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. Copyright © 2015 match.
Original languageEnglish
Pages (from-to)201-216
JournalMatch: Communications in mathematical and in computer chemistry
Volume74
Issue number1
Publication statusPublished - 2015

Citation

Chan, W. H., Xu, S.-J., & Nong, G. (2015). A linear-time algorithm for computing the complete forcing number and the clar number of catacondensed hexagonal systems. MATCH: Communications in Mathematical and in Computer Chemistry, 74(1), 201-216.

Fingerprint

Dive into the research topics of 'A linear-time algorithm for computing the complete forcing number and the clar number of catacondensed hexagonal systems'. Together they form a unique fingerprint.