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.