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

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.     

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.     

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.     

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.     

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.     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

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.     

Random Matchings in Regular Graphs

d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x. We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) : Theorem. For any d-regular graph G, (a) , so that , (b) , where the rates of convergence depend only on d. Received: April 12, 1996     

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.     

Group Weighted Matchings in Bipartite Graphs

Let G be a bipartite graph with bicoloration {A, B}, |A| = |B|, and let w : E(G) K where K is a finite abelian group with k elements. For a subset S E(G) let . A Perfect matching M E(G) is a w-matching if w(M) = 1.A characterization is given for all w's for which every perfect matching is a w-matching.It is shown that if G = K _k+1,k+1 then either G has no w-matchings or it has at least 2 w-matchings.If K is the group of order 2 and deg(a) d for all a A, then either G has no w-matchings, or G has at least (d – 1)! w-matchings.R. Meshulam: Research supported by a Technion V.P.R. Grant No. 100-854.     

Fan型条件对图的匹配的影响(英文)

设G是顶点数为2n且至多含有2(n-c)个奇分支的简单图(1≤c≤n).若不存在G的两个距离为2的顶点,其度均小于c-1,则G的边独立数至少为c,除非G含一类明显的禁用导出子图.特别,我们给出了Fan(-1)-型图含有1-因子的充要条件.     

Factor-Critical Graphs with Given Number of Maximum Matchings

A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with |V(G)| maximum matchings and with |V(G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized. This work is supported by the Ph.D. Programs Foundation of Ministry of Education of China (No.20070574006) and the NNSF(10201019) of China.     

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     

On Unicyclic Graphs with Uniquely Restricted Maximum Matchings

A graph is called unicyclic if it owns only one cycle. A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. Clearly, μ _r (G) ≤ μ(G), where μ _r (G) denotes the size of a maximum uniquely restricted matching, while μ(G) equals the matching number of G. In this paper we study unicyclic bipartite graphs enjoying μ _r (G) = μ(G). In particular, we characterize unicyclic bipartite graphs having only uniquely restricted maximum matchings. Finally, we present some polynomial time algorithms recognizing unicyclic bipartite graphs with (only) uniquely restricted maximum matchings.