Perfect Matchings of Generalized Polyomino Graphs

In this paper necessary and sufficient conditions are given for a generalized polyomino graph to have a perfect matching and to be elementary, respectively. The project was supported financially by National Natural Science Foundation of China (10431020).     

Existence of perfect matchings in a plane bipartite graph

We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).     

Snake graphs and continued fractions

This paper is a sequel to our previous work in which we found a combinatorial realization of continued fractions as quotients of the number of perfect matchings of snake graphs. We show how this realization reflects the convergents of the continued fractions as well as the Euclidean division algorithm. We apply our findings to establish results on sums of squares, palindromic continued fractions, Markov numbers and other statements in elementary number theory.     

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.     

The (conditional) matching preclusion for burnt pancake graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings, and the conditional matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph with no isolated vertices that has neither perfect matchings nor almost perfect matchings. In this paper, we find these two numbers for the burnt pancake graphs and show that every optimal (conditional) matching preclusion set is trivial.     

Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.     

Perfect matchings on a type of lattices with toroidal boundary

Enumeration of perfect matchings on graphs has a longstanding interest in combinatorial mathematics. In this paper, we obtain some explicit expressions of the number of perfect matchings for a type of Archimedean lattices with toroidal boundary by applying Tesler's crossing orientations to obtain some Pfaffan orientations and enumerating their Pfaffans.     

Enumerating Perfect Matchings in n-Cubes

The perfect matchings in the n-cube have earlier been enumerated for n?≤?6. A dynamic programming approach is here used to obtain the total number of perfect matchings in the 7-cube, which is 391 689 748 492 473 664 721 077 609 089. The number of equivalence classes of perfect matchings is further shown to be 336 in the 5-cube, 356 788 059 in the 6-cube and 607 158 046 495 120 886 820 621 in the 7-cube. The techniques used can be generalized to arbitrary bipartite and general graphs.     

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

On the Eigenvalue Two and Matching Number of a Tree

In [6],Guo and Tan have shown that 2 is a Laplacian eigenvalue of any tree with perfect matchings.For trees without perfect matchings,we study whether 2 is one of its Laplacian eigenvalues.If the matchingnumber is 1 or 2,the answer is negative;otherwise,there exists a tree with that matching number which has (hasnot) the eigenvalue 2.In particular,we determine all trees with matching number 3 which has the eigenvalue2.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

Direct Sum of Distributive Lattices on the Perfect Matchings of a Plane Bipartite Graph

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.     

关于图的运算与图的Pfaffian性

关于一般的图的完美匹配计数的问题已证实是NP-hard问题.但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决.由此可见图的Pfaffian性的重要性.在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.     

Matching structure and the matching lattice

The matching polyhedron, i.e., the convex hull of (incidence vectors of) perfect matchings of a graph was characterized by Edmonds; this result is the key to a large part of polyhedral combinatorics and is used in many combinatorial algorithms. The linear hull of perfect matchings was characterized by Naddef, and by Edmonds, Lovász, and Pulleyblank. In this paper we describe the lattice generated by these vectors, i.e., the set of all integer linear combinations of perfect matchings. It turns out that the Petersen graph is, in a sense, the only difficult example. Our results also imply a characterization of the linear hull of perfect matchings over fields of characteristic different from 0. The main method is a decomposition theory developed by Kotzig, Lovász, and Plummer, which breaks down every graph into a number of graphs called bricks with very good matching properties. The number of Petersen graphs among these bricks will turn out to be an essential parameter of the matching lattice. Some refinements of the decomposition theory are also given. Among others, we show that the list of bricks obtained during the decomposition procedure is independent of the special choices made during the procedure.     

Forcing matching numbers of fullerene graphs

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.     

Higher Dimensional Aztec Diamonds and a (2d + 2)-Vertex Model

Motivated by the close relationship between the number of perfect matchings of the Aztec diamond graph introduced in [5] and the free energy of the square-ice model, we consider a higher dimensional analog of this phenomenon. For d 1, we construct d-uniform hypergraphs which generalize the Aztec diamonds and we consider a companion d-dimensional statistical model (called the 2d + 2-vertex model) whose free energy is given by the logarithm of the number of perfect matchings of our hypergraphs. We prove that the limit defining the free energy per site of the 2d + 2-vertex model exists and we obtain bounds for it. As a consequence, we obtain an especially good asymptotical approximation for the number of matchings of our hypergraphs.     

Cell rotation graphs of strongly connected orientations of plane graphs with an application

The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T⁻, thus (T,T⁻) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T⁻, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height.     

Rank of maximum matchings in a graph

The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG. We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings.     

Sparsely intersecting perfect matchings in cubic graphs

In 1971, Fulkerson made a conjecture that every bridgeless cubic graph contains a family of six perfect matchings such that each edge belongs to exactly two of them; equivalently, such that no three of the matchings have an edge in common. In 1994, Fan and Raspaud proposed a weaker conjecture which requires only three perfect matchings with no edge in common. In this paper we discuss these and other related conjectures and make a step towards Fulkerson’s conjecture by proving the following result: Every bridgeless cubic graph which has a 2-factor with at most two odd circuits contains three perfect matchings with no edge in common.