Complete forcing numbers of graphs

Xin He, Heping Zhang


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.


Perfect matching, global forcing number, complete forcing number, cyclomatic number, wheel, cylinder

Full Text:



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