Details

Autor(en) / Beteiligte

• Zhou, Xiangqian
• Zhang, Heping

Titel

A minimax result for perfect matchings of a polyomino graph

Ist Teil von

• Discrete Applied Mathematics, 2016-06, Vol.206, p.165-171

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2016

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.