# A Maximum Resonant Set of Polyomino Graphs

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 2, page 323-337
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHeping Zhang, and Xiangqian Zhou. "A Maximum Resonant Set of Polyomino Graphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 323-337. <http://eudml.org/doc/277130>.

@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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.