Complete forcing numbers of graphs
Abstract
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.
Keywords
Perfect matching, global forcing number, complete forcing number, cyclomatic number, wheel, cylinder
Full Text:
MANUSCRIPTDOI: https://doi.org/10.26493/1855-3974.2706.3c8
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications