A Maximum Resonant Set of Polyomino Graphs
Zhang, Heping · Zhou, Xiangqian
Original · EN
A polyomino graph H 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. In this paper, we show that if K is a maximum resonant set of H, then H-K has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to its Clar number. Based on this result, we have that the maximum forcing number of a polyomino graph can be computed in polynomial time. We also show that if K is a maximal alternating set of H, then H-K has a unique perfect matching.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.