Complete forcing numbers of graphs
DOI:
https://doi.org/10.26493/1855-3974.2706.3c8Keywords:
Perfect matching, global forcing number, complete forcing number, cyclomatic number, wheel, cylinderAbstract
The complete forcing number of a graph G with a perfect matching is the minimum cardinality of an edge set of G on which the restriction of each perfect matching M is a forcing set of M. This concept can be view as a strengthening of the concept of global forcing number of G. Došlić in 2007 has obtained that the global forcing number of a connected graph is at most its cyclomatic number. Motivated from this result, we obtain that the complete forcing number of a graph is no more than 2 times its cyclomatic number and characterize the matching covered graphs whose complete forcing numbers attain this upper bound and minus one, respectively. Besides, we present a method of constructing a complete forcing set of a graph. By using such method, we give closed formulas for the complete forcing numbers of wheels and cylinders.Downloads
Published
2022-12-13
Issue
Section
Articles
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/