Perfect Matchings Of Plane Bipartite Graphs And Distributive Lattice Structures

Zhang Fuji et al. introduced Z-transformation graph (resonance graph) on the set of perfect matchings of hexagonal systems in 1988: two perfect matchings are adjacent if and only if they only differ in a hexagon. Later, Zhang Heping et al. extended this concept to the perfect matching set of plane bipartite graphs. By distinguishing two matching alternating cycles, they gave orientations on Z-transformation graphs and established Z-transformation digraphs. For plane weakly elementary bipartite graphs, they proved the Z-transformation digraphs have no directed cycles, and established distributive lattice structures on their perfect matching sets. According to the properties of this structure, Zhang Heping also proved that all connected Z-transformation graphs are median graphs and can be isometrically embedded into hypercubes. Since the concept of resonance graph is very natural, it was ever independently introduced by Grundler, Randic and Forunier.For a plane weakly bipartite graph G, let M(G) be the distributive lattice on the set of its perfect matchings determined by the Z-transformation digraph. A finite distributive lattice L is called a matchable distributive lattice if there exists a plane bipartite graph G, such that L (?) M(G). It is known that there exist some non-matchable distributive lattices. So a natural question is how to characterize matchable distributive lattices. We studied this question in two ways and give some classes of matchable and non-matchable distributive lattices. By the famous Birkhoff''s fundamental theorem of finite distributive lattices, the distributive lattice M(G) can be generated by its join-irreducible elements. Hence the second question is how to characterize join-irreducible elements of M(G). We give a complete characterization to sub-poset induced by join-irreducible elements of M(G) by establishing partial order on the multi-set of inner faces of G. Since matchable distributive lattices can be embedded into integral grids, we may ask what is the smallest dimension of the integral grids into which M(G) can be embedded. Zhang Heping conjectured this number is just the resonance number of G as early as in 1998. Basing on the above characterization of join-irreducible elements of M(G), we verify the conjecture.This thesis consists of six chapters. In the first chapter, we introduce some definitions and notations about graphs and distributive lattices. Then we summarize recent main results and investigation progresses about Z-transformation graphs and finite distributive lattice structures on the perfect matching set of plane bipartite graphs. In the end of this chapter, the main results of this thesis are listed. In Chapter 2, we establish a partial order on the set of inner faces of 2-connected outerplane bipartite graph G and by applying the famous Dilworth's min-max theorem on posets, we prove that the smallest number of e-cuts covering G equals to the dimension of a largest induced hypercube of its Z-transformation graph, which turns out to be the resonance number of G. This generalizes the corresponding min-max theorem found by Klavzar et al. on catacondensed benzenoid graphs.In Chapter 3 we consider two special classes of plane elementary bipartite graphs, 2-connected outerplane bipartite graphs and truncated parallelograms, and give two classes of matchable distributive lattices: J(T) and J(W), where T is an arbitrary tree-like poset, W is an arbitrary filter of direct product m×n of chains m and n, and J(P) is the finite distributive lattice constructed by all the filters of P according to reverse inclusion.In Chapter 4, by characterizing the local structures of matchable distributive lattices with cut-elements, we obtain several classes of non-matchable distributive lattices. We prove that L is a non-matchable distributive lattice if either L has an (m + n)-cut element such that m, n≥3 or L has a (2 + n)-cut element but contains no a special sub-lattice. Here an element x of L is called a cut element if x is neither maximum element nor minimum element and contained in all maximal chains of L. Furthermore, x is called an (m + n)-cut element if there are exactly m elements cover x and n elements are covered by x.In Chapter 5, we establish a poset F(G) on the multi-set of inner faces of a plane elementary bipartite graph G and then prove that M(G) (?) J(F(G)). By applying this result, we show that the minimum dimension of integral grids into which M(G) can be embedded is equal to the resonance number of G. Besides, we prove that J(1×m×n) is a matchable distributive lattice.In the last chapter, we establish quotient lattice and in-tree (forest) structures on an ordinary poset. We prove that if we restrict some elements in the process of constructing J(P), the resulting algebraic structure is the direct sum of finite distributive lattices. The equivalent relation induced by its components is a congruence on J(P), which producess a quotient lattice of J(P). We also show that dual in-trees constructed from P and its dual P* have the same height and width, which generalize the corresponding results on the set of perfect matchings of plane bipartite graphs.