Pachter, Lior and Kim, Peter (1998) Forcing matchings on square grids. Discrete Mathematics, 190 (1-3). pp. 287-294. ISSN 0012-365X. https://resolver.caltech.edu/CaltechAUTHORS:20170309-141622723
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170309-141622723
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.
| Item Type: | Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| 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. | |||||||||
| Funders: |
| |||||||||
| Subject Keywords: | Forcing number of a matching; Domino tiling; Feedback arc set | |||||||||
| Issue or Number: | 1-3 | |||||||||
| Record Number: | CaltechAUTHORS:20170309-141622723 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170309-141622723 | |||||||||
| Official Citation: | Lior Pachter, Peter Kim, Forcing matchings on square grids, Discrete Mathematics, Volume 190, Issue 1, 1998, Pages 287-294, ISSN 0012-365X, http://dx.doi.org/10.1016/S0012-365X(97)00266-5. (http://www.sciencedirect.com/science/article/pii/S0012365X97002665) | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 74995 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | George Porter | |||||||||
| Deposited On: | 10 Mar 2017 03:20 | |||||||||
| Last Modified: | 24 Feb 2020 10:30 |
Repository Staff Only: item control page
