کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418514 | 681678 | 2016 | 7 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 206, 19 June 2016, Pages 165–171