An upper bound for the number of perfect matchings in graphs

Details An upper bound for the number of perfect matchings in graphs An upper bound for the number of perfect matchings in graphs

2008-03-06

arxiv.org/abs/0803.0864v1

Mathematics

Combinatorics

6 pages

Scientific paper

We give an upper bound on the number of perfect matchings in an undirected simple graph $G$ with an even number of vertices, in terms of the degrees of all the vertices in $G$. This bound is sharp if $G$ is a union of complete bipartite graphs. This bound is a generalization of the upper bound on the number of perfect matchings in bipartite graphs on $n+n$ vertices given by the Bregman-Minc inequality for the permanents of $(0,1)$ matrices.

Affiliated with

Also associated with

No associations

Rating

An upper bound for the number of perfect matchings in 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 An upper bound for the number of perfect matchings in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An upper bound for the number of perfect matchings in graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-13811