A Distributive Lattice on the Set of Perfect Matchings of a Plane Bipartite Graph |
| |
Authors: | Peter Che Bor Lam Heping Zhang |
| |
Affiliation: | (1) Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, P.R. China |
| |
Abstract: | Let G be a plane bipartite graph and M(G) the set of perfect matchings of G. The Z-transformation graph of G is defined as a graph on M(G): M,MM(G) are joined by an edge if and only if they differ only in one cycle that is the boundary of an inner face of G. A property that a certain orientation of the Z-transformation graph of G is acyclic implies a partially ordered relation on M(G). An equivalent definition of the poset M(G) is discussed in detail. If G is elementary, the following main results are obtained in this article: the poset M(G) is a finite distributive lattice, and its Hasse diagram is isomorphic to the Z-transformation digraph of G. Further, a distributive lattice structure is established on the set of perfect matchings of any plane bipartite graph. |
| |
Keywords: | distributive lattice poset perfect matching Z-transformation graph plane bipartite graph |
本文献已被 SpringerLink 等数据库收录! |