Perfect matchings of generalized polyomino graphs. (English) Zbl 1089.05061

Summary: Necessary and sufficient conditions are given for a generalized polyomino graph to have a perfect matching and to be elementary, respectively.


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B50 Polyominoes
Full Text: DOI


[1] Lovász, L., Plummer, M.D.: Matching Theory (Annals of Discrete Mathematics 29). Amsterdam: North-Holland, 1986 · Zbl 0618.05001
[2] Plummer, M. D., Matching Theory - a sampler: from Dénes Konig to the present, Discrete Math., 100, 177-219 (1992) · Zbl 0774.05080
[3] Propp, J.: Enumeration of Matchings: Problems and Progress, MSRI Publications Vol 38, Cambridge Univ. Press, 1999, pp. 255-291 · Zbl 0937.05065
[4] Akiyama, J., Kano, M.: 1-factor of triangle graphs. In: Akiyama, J.: Number Theory and Combinatorics, World Scientific 1985, pp. 21-35 · Zbl 0605.05034
[5] Zhang, H. P.; Zhang, F. J., Perfect matchings of polyomino graphs, Graphs and Combinatorics, 13, 295-304 (1997) · Zbl 0895.05051
[6] Kostochka, A.V.: Proc. 30th Internat, Wiss, Koll TH Ilmenau. Vortragsreihe, E. 1985, pp. 49-52
[7] Zhang, F. J.; Guo, X. F.; Chen, R. S., Perfect matchings in hexagonal systems, Graphs and Combinatorics, 1, 383-386 (1985) · Zbl 0614.05043
[8] Cyvin, S.J., Brunvoll, J., Cyvin, B.N., Chen, R.S., Zhang, F.J.: Theory of Coronoid Hydrocarbons II. Springer, Berlin Heidelberg, 1994
[9] Kasteleyn, P. W., The statistics of dimer on a lattice I., The number of dimer arrangement on a quadratic lattice, Physica, 27, 1209-1225 (1961) · Zbl 1244.82014
[10] John, P.; Sachs, H.; Zerntic, H., Counting perfect matchings in polyominoes with applications to the dimer problem, Zastosowania Matemetyki (Appl.math), 19, 465-477 (1987) · Zbl 0718.05018
[11] Sachs, H.: Counting perfect matchings in lattice graphs, In: Topics in combinatorics and graph theory, Heidelberg: Physica-Verlag 1990, pp. 577-584 · Zbl 0735.05067
[12] Berge, C.; Chen, C. C.; Chvátal, V.; Soaw, C. S., Combinatorial properties of polyominoes, Combinatirica, 1, 217-224 (1981) · Zbl 0491.05048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.