Complete forcing numbers of primitive coronoids

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 restr...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2016-07, Vol.32 (1), p.318-330
Main Authors: Xu, Shou-Jun, Liu, Xiu-Song, Chan, Wai Hong, Zhang, Heping
Format: Article
Language:English
Subjects:
Combinatorics
Convex and Discrete Geometry
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ).
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-015-9881-y