Forcing numbers of stop signs

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.

Additional details