Geodesic
A Maximum Resonant Set of Polyomino Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 323-337

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: polyomino graph, dimer problem, perfect matching, resonant set, forcing number, alternating set 
@article{DMGT_2016_36_2_a5,
     author = {Zhang, Heping and Zhou, Xiangqian},
     title = {A {Maximum} {Resonant} {Set} of {Polyomino} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {323--337},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/}
}
TY  - JOUR
AU  - Zhang, Heping
AU  - Zhou, Xiangqian
TI  - A Maximum Resonant Set of Polyomino Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 323
EP  - 337
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/
LA  - en
ID  - DMGT_2016_36_2_a5
ER  - 
%0 Journal Article
%A Zhang, Heping
%A Zhou, Xiangqian
%T A Maximum Resonant Set of Polyomino Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 323-337
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/
%G en
%F DMGT_2016_36_2_a5
Zhang, Heping; Zhou, Xiangqian. A Maximum Resonant Set of Polyomino Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 323-337. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/