A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs

摘要

An essentially disconnected generalized polyomino graph is defined as a generalized polyomino graph with some perfect matchings and forbidden edges. The number of perfect matchings of a generalized polyomino graph G is the product of the number of perfect matchings of each elementary component in G. In this paper, we obtain a lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs.