Published August 28, 1998
| public
Journal Article
Forcing matchings on square grids
- Creators
-
Pachter, Lior
- Kim, Peter
Abstract
Let G be a graph that admits a perfect matching. The forcing number of a perfect matching M of G is defined as the smallest number of edges in a subset S ⊂ M, such that S is in no other perfect matching. We show that for the 2n × 2n square grid, the forcing number of any perfect matching is bounded below by n and above by n^2. Both bounds are sharp. We also establish a connection between the forcing problem and the minimum feedback set problem. Finally, we present some conjectures about forcing numbers in other graphs.
Additional Information
© 1998 Elsevier. Received 20 September 1996; revised 17 June 1997; accepted 13 October 1997. We thank Ken Halpern for discovering the example in Fig. 3. Dave Finberg helped in checking Conjecture 2. Lior Pachter was supported by DOE grant number 63564. Peter Kim was supported by the Center for Excellence in Education, while working at the RSI summer program.Additional details
- Eprint ID
- 74995
- Resolver ID
- CaltechAUTHORS:20170309-141622723
- 63564
- Department of Energy (DOE)
- Center for Excellence in Education
- Created
-
2017-03-10Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field