On the Number of Matchings in Regular Graphs

Details On the Number of Matchings in Regular Graphs On the Number of Matchings in Regular Graphs

2008-01-15

arxiv.org/abs/0801.2256v1

Mathematics

Combinatorics

26 pages, 4 figures

Scientific paper

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\le 4$.

Affiliated with

Also associated with

No associations

Rating

On the Number of Matchings in Regular Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Number of Matchings in Regular Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Number of Matchings in Regular Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-150796