A Distributive Lattice on the Set of Perfect Matchings of a Plane Bipartite Graph

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.     

Perfect Matchings of Regular Bipartite Graphs

Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.     

Distributive Lattices,Bipartite Graphs and Alexander Duality

A certain squarefree monomial ideal H _P arising from a finite partially ordered set P will be studied from viewpoints of both commutative algbera and combinatorics. First, it is proved that the defining ideal of the Rees algebra of H _P possesses a quadratic Gröbner basis. Thus in particular all powers of H _P have linear resolutions. Second, the minimal free graded resolution of H _P will be constructed explicitly and a combinatorial formula to compute the Betti numbers of H _P will be presented. Third, by using the fact that the Alexander dual of the simplicial complex Δ whose Stanley–Reisner ideal coincides with H _P is Cohen–Macaulay, all the Cohen–Macaulay bipartite graphs will be classified.     

渺位六角系统完美匹配Z——变换图

六角系统是2-连通的平面图，其每个内部面都是单位正六边形．六角系统的完美匹配是化学中苯类芳烃体系的Kekule结构．一个六角系统H完美匹配Z—变换图Z（H）是一个图，它的顶点集是H的完匹配集，两个匹配相邻当且仅当它们的对称差是一个单位正六边形．本文用乘积图刻划了沙位六角系统Z—变换图的结构．     

Characterization of Co-blockers for Simple Perfect Matchings in a Convex Geometric Graph

Consider the complete convex geometric graph on $2m$ 2 m vertices, CGG $(2m)$ ( 2 m ) , i.e., the set of all boundary edges and diagonals of a planar convex $2m$ 2 m -gon P. In (Keller and Perles, Israel J Math 187:465–484, 2012), the smallest sets of edges that meet all the simple perfect matchings (SPMs) in CGG $(2m)$ ( 2 m ) (called “blockers”) are characterized, and it is shown that all these sets are caterpillar graphs with a special structure, and that their total number is $m \cdot 2^{m-1}$ m · 2 m ? 1 . In this paper we characterize the co-blockers for SPMs in CGG $(2m)$ ( 2 m ) , that is, the smallest sets of edges that meet all the blockers. We show that the co-blockers are exactly those perfect matchings M in CGG $(2m)$ ( 2 m ) where all edges are of odd order, and two edges of M that emanate from two adjacent vertices of P never cross. In particular, while the number of SPMs and the number of blockers grow exponentially with m, the number of co-blockers grows super-exponentially.     

对称拓扑分子格的直和

文章给出了对称拓扑分子格的直和概念,给出了拓扑分子格的直和的特征,证明了对称拓扑分子格的分离性Ti(i=-1,0,1,2)及可数性CⅠ,CⅡ是可和性质.     

Perfect Matchings Avoiding Several Independent Edges in a Star‐Free Graph

In Aldred and Plummer (Discrete Math 197/198 (1999) 29–40) proved that every m‐connected ‐free graph of even order has a perfect matching M with and , where F₁ and F₂ are prescribed disjoint sets of independent edges with and . It is known that if l satisfies , then the star‐free condition in the above result is best possible. In this paper, for , we prove a refinement of the result in which the condition is replaced by the weaker condition that G is ‐free (note that the new condition does not depend on l). We also show that if m is even and either or , then for m‐connected graphs G with sufficiently large order, one can replace the condition by the still weaker condition that G is ‐free. The star‐free conditions in our results are best possible.     

二部图上完美匹配的正交匹配分解

给定简单二部图G=（V，E），最大度是k（k≥3），G有一个完美匹配M={e1，e2，…，ek}。称边集E的划分{E1，E2，…，El}是G的一个关于肼的正交匹配分解，如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G，存在关于完美匹配肼的正交匹配分解，并给出了求这个分解的多项式时间算法。     

和图、整和图与模和图的几个结果

Let N denote the set of positive integers. The sum graph G^＋（S） of a finite subset S belong to N is the graph （S, E） with uv ∈ E if and only if u ＋ v ∈ S. A graph G is said to be a sum graph if it is isomorphic to the sum graph of some S belong to N. By using the set Z of all integers instead of N, we obtain the definition of the integral sum graph. A graph G = （V, E） is a mod sum graph if there exists a positive integer z and a labelling, λ, of the vertices of G with distinct elements from {0, 1, 2,..., z - 1} so that uv ∈ E if and only if the sum, modulo z, of the labels assigned to u and v is the label of a vertex of G. In this paper, we prove that flower tree is integral sum graph. We prove that Dutch m-wind-mill （Dm） is integral sum graph and mod sum graph, and give the sum number of Dm.     

和图、整和图及模和图的几个结果

Let N denote the set of positive integers.The sum graph G (S) of a finite subset S (C) N is the graph (S,E) with uv ∈ E if and only if u v ∈ S.A graph G is said to be a sum graph if it is isomorphic to the sum graph of some S С N.By using the set Z of all integers instead of N,we obtain the definition of the integral sum graph.A graph G=(V,E) is a mod sum graph if there exists a positive integer z and a labelling,λ,of the vertices of G with distinct elements from {0,1,2,...,z-1} so that uv ∈ E if and only if the sum,modulo z,of the labels assigned to u and v is the label of a vertex of G.In this paper,we prove that flower tree is integral sum graph.We prove that Dutch m-wind-mill (Dm) is integral sum graph and mod sum graph,and give the sum number of Dm.     

Pseudo-Complementation on Almost Distributive Lattices

The concept of a pseudo-complementation * on an almost distributive lattice (ADL) with 0 is introduced and it is proved that it is equationally definable. A one-to-one correspondence between the pseudo-complementations on an ADL L with 0 and maximal elements of L is obtained. It is also proved that L* = {a*|a L} is a Boolean algebra which is independent (upto isomorphism) of the pseudo-complementation * on L.AMS Subject Classification (1991): 06D99 06D15     

Distributive Lattices with a Negation Operator

In this note we introduce and study algebras (L, V, Λ, ?, 0,1) of type (2, 2,1,1,1) such that (L, V, ?, 0,1) is a bounded distributive lattice and ? is an operator that satisfies the condition ? (a V b) = a ? b and ? 0 = 1. We develop the topological duality between these algebras and Priestley spaces with a relation. In addition, we characterize the congruences and the subalgebras of such an algebra. As an application, we will determine the Priestley spaces of quasi-Stone algebras.     

Computability of Distributive Lattices

The class of (not necessarily distributive) countable lattices is HKSS-universal, and it is also known that the class of countable linear orders is not universal with respect to degree spectra neither to computable categoricity. We investigate the intermediate class of distributive lattices and construct a distributive lattice with degree spectrum {d: d ≠ 0}. It is not known whether a linear order with this property exists. We show that there is a computably categorical distributive lattice that is not relatively Δ₂⁰-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.     

Perfect Matchings of Polyomino Graphs

This paper gives necessary and sufficient conditions for a polyomino graph to have a perfect matching and to be elementary, respectively. As an application, we can decompose a non-elementary polyomino with perfect matchings into a number of elementary subpolyominoes so that the number of perfect matchings of the original non-elementary polyomino is equal to the product of those of the elementary subpolyominoes.     

Involutive Residuated Lattices Based on Modular and Distributive Lattices

An involutive residuated lattice (IRL) is a lattice-ordered monoid possessing residual operations and a dualizing element. We show that a large class of self-dual lattices may be endowed with an IRL structure, and give examples of lattices which fail to admit IRLs with natural algebraic conditions. A classification of all IRLs based on the modular lattices M _n is provided.     

Perfect Matchings of Cellular Graphs

We introduce a family of graphs, called cellular, and consider the problem of enumerating their perfect matchings. We prove that the number of perfect matchings of a cellular graph equals a power of 2 times the number of perfect matchings of a certain subgraph, called the core of the graph. This yields, as a special case, a new proof of the fact that the Aztec diamond graph of order n introduced by Elkies, Kuperberg, Larsen and Propp has exactly 2 ^n(n+1)/2 perfect matchings. As further applications, we prove a recurrence for the number of perfect matchings of certain cellular graphs indexed by partitions, and we enumerate the perfect matchings of two other families of graphs called Aztec rectangles and Aztec triangles.     

Graphs of Non-Crossing Perfect Matchings

 Let P _n be a set of n=2m points that are the vertices of a convex polygon, and let ℳ _m be the graph having as vertices all the perfect matchings in the point set P _n whose edges are straight line segments and do not cross, and edges joining two perfect matchings M ₁ and M ₂ if M ₂=M ₁−(a,b)−(c,d)+(a,d)+(b,c) for some points a,b,c,d of P _n . We prove the following results about ℳ _m : its diameter is m−1; it is bipartite for every m; the connectivity is equal to m−1; it has no Hamilton path for m odd, m>3; and finally it has a Hamilton cycle for every m even, m≥4. Received: October 10, 2000 Final version received: January 17, 2002 RID="*" ID="*" Partially supported by Proyecto DGES-MEC-PB98-0933 Acknowledgments. We are grateful to the referees for comments that helped to improve the presentation of the paper.     

完全分配格上的点式拟一致结构

本文在完全分配格上建立了一种点式拟一致结构理论，许多一般拓扑中的相应定理都被得到了。特别地，我们证明了每个拓扑分子格都可以拟一致化。此外，还讨论了乘积拟一致分子格的拓扑结构。     

完全分配格上的良Urysohn性

本文目的是在无逆序对合的分配格上研究余拓扑的Urysohn性质，利用coHeyting代数的pseudo-negation和分子的linked component的概念，在完全分配格上定义了一种新的Urysohn性质，称之为良Urysohn性．文中详细地讨论良Urysohn性的基本性质，并利用文中建立的Urysohn收敛理论给出了良Urysohn性的刻画定理．     

On Vertex-Disjoint Complete Bipartite Subgraphs in a Bipartite Graph

 We show that, if G=(X,Y;E) is a bipartite graph with |X|=|Y|=4s and δ(G)≥4s−3 for any integer s≥2, then G contains four vertex-disjoint copies of K _s,s. This constitutes a partial answer to a conjecture in [4]. Received: March 27, 1996 Revised: March 7, 1997