(1) Department of Informatics and Mathematics, Faculty of Agriculture, University of Zagreb, Svetošimunska c. 25, 10000 Zagreb, CROATIA
Abstract:
In the first part of this paper we establish sharp lower bounds on the number of perfect matchings in benzenoid graphs and polyominoes. The results are then used to determine which integers can appear as the number of perfect matchings of infinitely many benzenoids and/or polyominoes. Finally, we consider the problem of concealed non-Kekuléan polyominoes. It is shown that the smallest such polyomino has 15 squares, and that such polyominoes on n squares exist for all n ≥ 15.