A minimax result for perfect matchings of a polyomino graph

作者：Zhou, Xiangqian; Zhang, Heping^*

来源：Discrete Applied Mathematics, 2016, 206: 165-171.

DOI：10.1016/j.dam.2016.01.033

• Polyomino graph
• Perfect matching
• Resonant set
• Forcing number

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.

• 出版日期2016-6-19
• 单位兰州大学