Perfect Matchings and Perfect Powers

In the last decade there have been many results about special families of graphs whose number of perfect matchings is given by perfect or near perfect powers (N. Elkies et al., J. Algebraic Combin. 1 (1992), 111–132; B.-Y. Yang, Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA, 1991; J. Propp, New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999). In this paper we present an approach that allows proving them in a unified way. We use this approach to prove a conjecture of James Propp stating that the number of tilings of the so-called Aztec dungeon regions is a power (or twice a power) of 13. We also prove a conjecture of Matt Blum stating that the number of perfect matchings of a certain family of subgraphs of the square lattice is a power of 3 or twice a power of 3. In addition we obtain multi-parameter generalizations of previously known results, and new multi-parameter exact enumeration results. We obtain in particular a simple combinatorial proof of Bo-Yin Yang's multivariate generalization of fortresses, a result whose previously known proof was quite complicated, amounting to evaluation of the Kasteleyn matrix by explicit row reduction. We also include a new multivariate exact enumeration of Aztec diamonds, in the spirit of Stanley's multivariate version.     

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.     

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.     

Perfect Matchings Versus Odd Cuts

We give a simple proof for an important result of Edmonds, Lovász and Pulleyblank, stating that a brick has no non-trivial tight cuts. Our proof relies on some results on almost critical graphs. The introduction of these graphs is the second aim of the present paper.     

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.     

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.     

Forbidden Induced Subgraphs for Perfect Matchings

Let ${\mathcal{F}}$ be a family of connected graphs. A graph G is said to be ${\mathcal{F}}$ -free if G is H-free for every graph H in ${\mathcal{F}}$ . We study the problem of characterizing the families of graphs ${\mathcal{F}}$ such that every large enough connected ${\mathcal{F}}$ -free graph of even order has a perfect matching. This problems was previously studied in Plummer and Saito (J Graph Theory 50(1):1–12, 2005), Fujita et al. (J Combin Theory Ser B 96(3):315–324, 2006) and Ota et al. (J Graph Theory, 67(3):250–259, 2011), where the authors were able to characterize such graph families ${\mathcal{F}}$ restricted to the cases ${|\mathcal{F}|\leq 1, |\mathcal{F}| \leq 2}$ and ${|\mathcal{F}| \leq 3}$ , respectively. In this paper, we complete the characterization of all the families that satisfy the above mentioned property. Additionally, we show the families that one gets when adding the condition ${|\mathcal{F}| \leq k}$ for some k ≥ 4.     

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).     

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.     

Graphs of Triangulations and Perfect Matchings

Given a set P of points in general position in the plane, the graph of triangulations of P has a vertex for every triangulation of P, and two of them are adjacent if they differ by a single edge exchange. We prove that the subgraph of , consisting of all triangulations of P that admit a perfect matching, is connected. A main tool in our proof is a result of independent interest, namely that the graph that has as vertices the non-crossing perfect matchings of P and two of them are adjacent if their symmetric difference is a single non-crossing cycle, is also connected.     

Ordering Trees with Nearly Perfect Matchings by Algebraic Connectivity

Let T2k＋1 be the set of trees on 2k＋1 vertices with nearly perfect matchings and α（T） be the algebraic connectivity of a tree T. The authors determine the largest twelve values of the algebraic connectivity of the trees in T2k＋1. Specifically, 10 trees T2,T3,... ,T11 and two classes of trees T（1） and T（12） in T2k＋1 are introduced. It is shown in this paper that for each tree T^′1,T^″1∈T（1）and T^′12,T^″12∈T（12） and each i,j with 2≤i〈j≤11,α（T^′1）=α（T^″1）〉α（Tj）〉α（T^′12）=α（T^″12）.It is also shown that for each tree T with T∈T2k＋1／（T（1）∪{T2,T3,…,T11}∪T（12））,α（T^′12）〉α（T）.     

Perfect Matchings in Total Domination Critical Graphs

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3 _t EC graph is a total domination edge-critical graph with total domination number 3 and a 3 _t VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G − v has a perfect matching for every vertex v in G. In this paper, we show that every 3 _t EC graph of even order has a perfect matching, while every 3 _t EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3 _t VC graph of even order that is K _1,7-free has a perfect matching, while every 3 _t VC graph of odd order that is K _1,6-free is factor-critical. We show that these results are tight in the sense that there exist 3 _t VC graphs of even order with no perfect matching that are K _1,8-free and 3 _t VC graphs of odd order that are K _1,7-free but not factor-critical.     

On the Perfect Matchings of Near Regular Graphs

Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any v ? V(G){v \in V(G)}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least ?k/3?{\lfloor k/3\rfloor} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least ?k/2?{\lfloor k/2\rfloor} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least ?\fracn3?+1+(k-n){\lfloor\frac{n}3\rfloor+1+(k-n)} disjoint perfect matchings if h = k + 1.     

Laplacian Spectral Radius and Maximum Degree of Trees with Perfect Matchings

Let μ(T) and Δ(T) denote the Laplacian spectral radius and the maximum degree of a tree T, respectively. Denote by ${\mathcal{T}_{2m}}$ the set of trees with perfect matchings on 2m vertices. In this paper, we show that for any ${T_1, T_2\in\mathcal{T}_{2m}}$ , if Δ(T ₁) > Δ(T ₂) and ${\Delta(T_1)\geq \lceil\frac{m}{2}\rceil+2}$ , then μ(T ₁) > μ(T ₂). By using this result, the first 20th largest trees in ${\mathcal{T}_{2m}}$ according to their Laplacian spectral radius are ordered. We also characterize the tree which alone minimizes (resp., maximizes) the Laplacian spectral radius among all the trees in ${\mathcal{T}_{2m}}$ with an arbitrary fixed maximum degree c (resp., when ${c \geq \lceil\frac{m}{2}\rceil + 1}$ ).     

多边形链图中的完美匹配数

多边形链图的完美匹配数（即多边形碳氢链状聚合物的Ｋｅｋｕｌｅ结构数）是数学化学研究的重要内容之一。我们给出了一个求该数的简洁算法,并证明该数是一个多项式。做为应用,对于一类特殊的多边形链图,给出了具体的表达式。     

3-正则图的不共边的完美匹配（英文）

研究3-正则图的一个有意义的问题是它是否存在k个没有共边的完美匹配.关于这个问题有一个著名的Fan-Raspaud猜想：每一个无割边的3-正则图都有3个没有共边的完美匹配.但这个猜想至今仍未解决.设dim（P（G））表示图G的完美匹配多面体的维数.本文证明了对于无割边的3-正则图G,如果dim（P（G））≤14,那么k≤4：如果dim（P（G））≤20,那么k≤5.     

On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets

Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M₁ and M₂ be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M₁ and M₂ intersect at most |M₁|+|M₂|−1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp. Supported by PAPIIT(UNAM) of México, Proyecto IN110802 Supported by FAI-UASLP and by CONACYT of México, Proyecto 32168-E Supported by CONACYT of México, Proyecto 37540-A     

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

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

Extremal Graphs With a Given Number of Perfect Matchings

Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem.