Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872368 | Discrete Applied Mathematics | 2014 | 10 Pages |
Abstract
A distributive lattice structure M(G) has been established on the set of perfect matchings of a plane bipartite graph G. We call a lattice matchable distributive lattice (simply MDL) if it is isomorphic to such a distributive lattice. It is natural to ask which lattices are MDLs. We show that if a plane bipartite graph G is elementary, then M(G) is irreducible. Based on this result, a decomposition theorem on MDLs is obtained: a finite distributive lattice L is an MDL if and only if each factor in any cartesian product decomposition of L is an MDL. Two types of MDLs are presented: J(mÃn) and J(T), where mÃn denotes the cartesian product between m-element chain and n-element chain, and T is a poset implied by any orientation of a tree.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Heping Zhang, Dewu Yang, Haiyuan Yao,