CaltechAUTHORS
  A Caltech Library Service

Forcing matchings on square grids

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:
URLURL TypeDescription
http://dx.doi.org/10.1016/S0012-365X(97)00266-5DOIArticle
http://www.sciencedirect.com/science/article/pii/S0012365X97002665PublisherArticle
ORCID:
AuthorORCID
Pachter, Lior0000-0002-9164-6231
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:
Funding AgencyGrant Number
Department of Energy (DOE)63564
Center for Excellence in EducationUNSPECIFIED
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