On the number of matchings in regular graphs (Q1010842)

Summary: 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\leq 4\).