- Tytuł:
- A Maximum Resonant Set of Polyomino Graphs
- Autorzy:
-
Zhang, Heping
Zhou, Xiangqian - Powiązania:
- https://bibliotekanauki.pl/articles/31340955.pdf
- Data publikacji:
- 2016-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
polyomino graph
dimer problem
perfect matching
resonant set
forcing number
alternating set - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 323-337
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł