Advertisement
Published in:
01-05-2015
Complete forcing numbers of catacondensed hexagonal systems
Published in: Journal of Combinatorial Optimization | Issue 4/2015
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 matchings of G. A global forcing set of \(G\), introduced by Vukičević et al., is a subset of \(E(G)\) on which there are distinct restrictions of any two different perfect matchings of \(G\). Combining the above “forcing” and “global” ideas, we introduce and define a complete forcing set of G as a subset of \(E(G)\) on which the restriction of any perfect matching \(M\) of \(G\) is a forcing set of \(M\). The minimum cardinality of complete forcing sets is the complete forcing number of \(G\). First we establish some initial results about these two novel concepts, including a criterion for a complete forcing set, and comparisons between the complete forcing number and global forcing number. Then we give an explicit formula for the complete forcing number of a hexagonal chain. Finally a recurrence relation for the complete forcing number of a catacondensed hexagonal system is derived.