Bounds on the forcing numbers of bipartite graphs

The forcing number of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matching of G  . In this paper, we demonstrate several techniques to produce upper bounds on the forcing number of bipartite graphs. We present a simple method of showing that the maximum forcing number on the 2m×2n2m×2n rectangle is mn  , and show that the maximum forcing number on the 2m×2n2m×2n torus is also mn. Further, we investigate the lower bounds on the forcing number and determine the conditions under which a previously formulated lower bound is sharp; we provide an example of a family of graphs for which it is arbitrarily weak.