A Maximum Resonant Set of Polyomino Graphs

• Autorzy: Heping Zhang , Xiangqian Zhou
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

polyomino graph; dimer problem; perfect matching; resonant set; forcing number; alternating set

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 2
• Strony: 323-337

Daty

wydano

2016-05-01

otrzymano

2015-02-09

poprawiono

2015-06-29

zaakceptowano

2015-06-29

online

2016-04-15

Twórcy

autor

Heping Zhang

• School of Mathematics and Statistics Lanzhou University Lanzhou, Gansu 730000, P.R. China,

autor

Xiangqian Zhou

• School of Mathematics and Statistics Lanzhou University Lanzhou, Gansu 730000, P.R. China,

Identyfikatory

DOI

10.7151/dmgt.1857