Article ID Journal Published Year Pages File Type
6872368 Discrete Applied Mathematics 2014 10 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,