Complete forcing numbers of graphs

Xin He, Heping Zhang

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:

MANUSCRIPT


DOI: 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