Complete forcing numbers of graphs - He, Xin (Ars mathematica contemporanea, 2023)
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$?. T. Došlić J. Math. Chem. 41, No. 3, 217-229 (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: ciklomatsko število; complete forcing number; cyclomatic number; cylinder; global forcing number; globalno določitveno število; kolo; perfect matching; polno določitveno število; popolno prirejanje; valj; wheel