Complete forcing numbers of graphs

Authors

DOI:

https://doi.org/10.26493/1855-3974.2706.3c8

Keywords:

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

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.

Published

2022-12-13

Issue

Section

Articles