PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 2 | 323-337
Tytuł artykułu

A Maximum Resonant Set of Polyomino Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
2
Strony
323-337
Opis fizyczny
Daty
wydano
2016-05-01
otrzymano
2015-02-09
poprawiono
2015-06-29
zaakceptowano
2015-06-29
online
2016-04-15
Twórcy
autor
  • School of Mathematics and Statistics Lanzhou University Lanzhou, Gansu 730000, P.R. China, zhanghp@lzu.edu.cn
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1857
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.