Direct Sum of Distributive Lattices on the Perfect Matchings of a Plane Bipartite Graph |
| |
Authors: | Heping Zhang |
| |
Institution: | 1.School of Mathematics and Statistics,Lanzhou University,Lanzhou,Peoples’ Republic of China |
| |
Abstract: | Let G be a plane bipartite graph and M(G){\cal M}(G) the set of perfect matchings of G. A property that the Z-transformation digraph of perfect matchings of G is acyclic implies a partially ordered relation on M(G){\cal M}(G). It was shown that M(G){\cal M}(G) is a distributive lattice if G is (weakly) elementary. Based on the unit decomposition of alternating cycle systems, in this article we show that the poset
M(G){\cal M}(G) is direct sum of finite distributive lattices if G is non-weakly elementary; Further, if G is elementary, then the height of distributive lattice M(G){\cal M}(G) equals the diameter of Z-transformation graph, and both quantities have a sharp upper bound
é\fracn(n+2)4ù\lceil\frac{n(n+2)}{4}\rceil, where n denotes the number of inner faces of G. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|