A Maximum Resonant Set of Polyomino Graphs

@article{HepingZhang2016,
abstract = {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.},
author = {Heping Zhang, Xiangqian Zhou},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {polyomino graph; dimer problem; perfect matching; resonant set; forcing number; alternating set},
language = {eng},
number = {2},
pages = {323-337},
title = {A Maximum Resonant Set of Polyomino Graphs},
url = {http://eudml.org/doc/277130},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Heping Zhang
AU - Xiangqian Zhou
TI - A Maximum Resonant Set of Polyomino Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 323
EP - 337
AB - 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.
LA - eng
KW - polyomino graph; dimer problem; perfect matching; resonant set; forcing number; alternating set
UR - http://eudml.org/doc/277130
ER -