Article ID Journal Published Year Pages File Type
418514 Discrete Applied Mathematics 2016 7 Pages PDF
Abstract

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

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,