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. doi:10.1016/S0304-3975(02)00499-1.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2002 Elsevier.
Issue or Number:2-3
Record Number:CaltechAUTHORS:20170308-151538288
Persistent URL:
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, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74931
Deposited By: George Porter
Deposited On:09 Mar 2017 15:38
Last Modified:15 Nov 2021 16:29

Repository Staff Only: item control page