Let G be a plane bipartite graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M such that S is not contained by other perfect matchings of G. The minimum cardinality of forcing sets of M is called the forcing number of M, denoted by f (G, M). Pachter and Kim established a minimax result: for any perfect matching M of G, f (G, M) is equal to the maximum number of disjoint M-alternating cycles in G. For a polyomino graph H, we show that for every perfect matching M of H with the maximum or second maximum forcing number, f (H, M) is equal to the maximum number of disjoint M-alternating squares in H. This minimax result does not hold in general for other perfect matchings of H with smaller forcing number. (C) 2016 Elsevier B.V. All rights reserved.
展开▼
