Complete forcing numbers of primitive coronoids

Shou-Jun Xu (), Xiu-Song Liu (), Wai Hong Chan () and Heping Zhang ()
Additional contact information
Shou-Jun Xu: Lanzhou University
Xiu-Song Liu: Lanzhou University
Wai Hong Chan: The Hong Kong Institute of Education
Heping Zhang: Lanzhou University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 21, 318-330

Abstract: Abstract Let $$G$$ G be a graph with edge set $$E(G)$$ E ( G ) that admits a perfect matching $$M$$ M . A forcing set of $$M$$ M is a subset of $$M$$ M contained in no other perfect matching of $$G$$ G . A complete forcing set of $$G$$ G , recently introduced by Xu et al. (J Combin Optim 29(4):803–814, 2015c), is a subset of $$E(G)$$ 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$$ G is the complete forcing number of $$G$$ 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).

Keywords: Kekulé structure; Perfect matching; Forcing set; Complete forcing set; Global forcing set; Complete forcing number; Primitive coronoid (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9881-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:1:d:10.1007_s10878-015-9881-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9881-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().