Complete forcing numbers of primitive coronoids

Shou-Jun XU, Xiu-Song LIU, Wai Hong CHAN, Heping ZHANG

Research output: Contribution to journalArticle

2 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. (J Combin Optim 29(4):803–814, 2015c), is a subset of E(G) to which the restriction of any perfect matching is a forcing set of the perfect matching. The minimum possible cardinality of a complete forcing set of G is the complete forcing number of G. Previously, Xu et al. (J Combin Optim 29(4):803–814, 2015c) gave an expression for the complete forcing number of a hexagonal chain and a recurrence relation for complete forcing numbers of catacondensed hexagonal systems. In this article, by the constructive proof, we give an explicit analytical expression for the complete forcing number of a primitive coronoid, a circular single chain consisting of congruent regular hexagons (i.e., Theorem 3.9). Copyright © 2015 Springer Science+Business Media New York.
Original languageEnglish
Pages (from-to)318-330
JournalJournal of Combinatorial Optimization
Volume32
Issue number1
Early online dateApr 2015
DOIs
Publication statusPublished - Jul 2016

Fingerprint

Forcing
Perfect Matching
Industry
Hexagon
Subset
Congruent
Recurrence relation
Cardinality
Restriction
Graph in graph theory
Theorem

Citation

Xu, S.-J., Liu, X.-S., Chan, W. H., Zhang, H. (2016). Complete forcing numbers of primitive coronoids. Journal of Combinatorial Optimization, 32(1), 318-330.

Keywords

  • Kekulé structure
  • Perfect matching
  • Forcing set
  • Complete forcing set
  • Global forcing set
  • Complete forcing number
  • Primitive coronoid