Forcing matchings on square grids |
| |
Authors: | Lior Pachter Peter Kim |
| |
Affiliation: | Department of Mathematics, MIT, Cambridge, MA 02139, USA |
| |
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 n2. 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. |
| |
Keywords: | Forcing number of a matching Domino tiling Feedback arc set |
本文献已被 ScienceDirect 等数据库收录! |
|