Abstract
We show that the number of perfect matchings in a simple graph G with an even number of vertices and degree sequence d1, d2,..., dn is at most ∏i=1n(di· !)1/2di. This bound is sharp if and only if G is a union of complete balanced bipartite graphs.
Original language | English (US) |
---|---|
Article number | N13 |
Journal | Electronic Journal of Combinatorics |
Volume | 15 |
Issue number | 1 N |
DOIs | |
State | Published - Apr 24 2008 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics
Keywords
- Perfect matchings
- Permanents