Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: polyomino graph

Sortuj według:

Ogranicz wyniki do:

A Maximum Resonant Set of Polyomino Graphs

100%

Zhang H., Zhou X.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 2

323-337

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Zhang H.

1 Zhou X.

1 2016

Wyniki wyszukiwania

A Maximum Resonant Set of Polyomino Graphs