CaltechAUTHORS
  A Caltech Library Service

Forcing numbers of stop signs

Lam, Fumei and Pachter, Lior (2003) Forcing numbers of stop signs. Theoretical Computer Science, 303 (2-3). pp. 409-416. ISSN 0304-3975. https://resolver.caltech.edu/CaltechAUTHORS:20170308-151538288

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:20170308-151538288

Abstract

Let G be a graph with a perfect matching M. The forcing number of M is the smallest number of edges in a subset S⊂M such that S is contained in no other perfect matching of G. We present methods for determining bounds on forcing numbers and apply these methods to find bounds for the forcing numbers of stop signs. A consequence of our main result is that every perfect matching of a stop sign of size (n,k) contains at least n disjoint alternating cycles.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/S0304-3975(02)00499-1DOIArticle
http://www.sciencedirect.com/science/article/pii/S0304397502004991PublisherArticle
ORCID:
AuthorORCID
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2002 Elsevier.
Issue or Number:2-3
Record Number:CaltechAUTHORS:20170308-151538288
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170308-151538288
Official Citation:Fumei Lam, Lior Pachter, Forcing numbers of stop signs, Theoretical Computer Science, Volume 303, Issue 2, 2003, Pages 409-416, ISSN 0304-3975, http://dx.doi.org/10.1016/S0304-3975(02)00499-1. (http://www.sciencedirect.com/science/article/pii/S0304397502004991)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74931
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:09 Mar 2017 15:38
Last Modified:24 Feb 2020 10:30

Repository Staff Only: item control page