Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651265 | Discrete Mathematics | 2006 | 8 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Seth Kleinerman,