A maximum resonant set of polyomino graphs
Heping Zhang, Xiangqian Zhou · Discussiones Mathematicae Graph Theory · 2015
A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square.A dimer covering of P corresponds to a perfect matching.Different dimer coverings can interact via an alternating cycle (or square) with respect to them.A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M -alternating.In this paper, we show that if K is a maximum resonant set of P , then P -K has a unique perfect matching.We further prove that the maximum forcing number of a polyomino graph is equal to the cardinality of a maximum resonant set.This confirms a conjecture of Xu et al. [26].We also show that if K is a maximal alternating set of P , then P -K has a unique perfect matching.