两类四角系统的匹配数与点独立集数

The Num bers of Matchings and Independent-Sets with Respectto the Polyom inoes Ln and Zn

给出了两类四角系统的完美匹配数。

LetGbe a graph. Denote m (G) the num ber ofperfect m atchings in G and μ(G), σ(G) the num bers ofm atchings and independent sets in Grespectively. A polyom ino (graph) is a connected finite sub graph ofthe infinite plane grid such thateach interior face is surrounded by a unitsquare and each edge be longs to at leastone square. The set of polyom inoes containing n unit squars is denoted by Pn. Suppose Ln and Zn are the linear chain and zigzag chain in Pn. In this paper, w e give form ulae to calculate m (G), μ(G) and σ(G), w here G= Ln, Zn.