The maximum number of perfect matchings in graphs with a given degree sequence (Q1010667)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The maximum number of perfect matchings in graphs with a given degree sequence |
scientific article |
Statements
The maximum number of perfect matchings in graphs with a given degree sequence (English)
0 references
7 April 2009
0 references
Summary: We show that the number of perfect matchings in a simple graph \(G\) with an even number of vertices and degree sequence \(d_1,d_2, \dots ,d_n\) is at most \(\pi_{i=1}^n (d_i!)^{\frac{1}{2d_i}}\). This bound is sharp if and only if \(G\) is a union of complete balanced bipartite graphs.
0 references
perfect matchings
0 references
permanents
0 references
complete balanced bipartite graphs
0 references