On the Number of Matchings in Regular Graphs

2008/01/15 by Friedland, S., Krop, E., Markström, K. · 1 citation
#05A15 #05A16 #05C70 #05C80 #82B20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0801.2256

Abstract

For the set of graphs with a given degree sequence, consisting of any number of 2's and 1's, and its subset of bipartite graphs, we characterize the optimal graphs who maximize and minimize the number of m-matchings. We find the expected value of the number of m-matchings of r-regular bipartite graphs on 2n vertices with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for m-matchings in r-regular bipartite graphs on 2n vertices, and their asymptotic versions for infinite r-regular bipartite graphs. We prove these conjectures for 2-regular bipartite graphs and for m-matchings with m≤ 4.

Cited by

• Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs

Related

• Results and open problems in matchings in regular graphs
• Counting matchings in irregular bipartite graphs and random lifts
• Matchings and Independent Sets of a Fixed Size in Regular Graphs
• Matchings in regular graphs: minimizing the partition function
• Asymptotics of the Upper Matching Conjecture