Bounds on the forcing numbers of bipartite graphs |
| |
Authors: | Seth Kleinerman |
| |
Institution: | Department of Mathematics, Harvard University, Cambridge, MA 02138, USA |
| |
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×2n rectangle is mn, and show that the maximum forcing number on the 2m×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: | Forcing number Perfect matching Torus |
本文献已被 ScienceDirect 等数据库收录! |
|