Complete forcing numbers of catacondensed hexagonal systems

Shou-Jun Xu (), Heping Zhang () and Jinzhuan Cai ()
Additional contact information
Shou-Jun Xu: Lanzhou University
Heping Zhang: Lanzhou University
Jinzhuan Cai: Hainan University

Journal of Combinatorial Optimization, 2015, vol. 29, issue 4, No 9, 803-814

Abstract: 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$$ G , introduced by Vukičević et al., is a subset of $$E(G)$$ E ( G ) on which there are distinct restrictions of any two different perfect matchings of $$G$$ G . Combining the above “forcing” and “global” ideas, we introduce and define a complete forcing set of G as a subset of $$E(G)$$ E ( G ) on which the restriction of any perfect matching $$M$$ M of $$G$$ G is a forcing set of $$M$$ M . The minimum cardinality of complete forcing sets is the complete forcing number of $$G$$ 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.

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

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9624-x 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:29:y:2015:i:4:d:10.1007_s10878-013-9624-x

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

DOI: 10.1007/s10878-013-9624-x

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 ().