The maximum number of perfect matchings in graphs with a given degree sequence
Noga AlonShmuel Friedland
所有作者
Noga AlonShmuel Friedland
文献摘要
We show that the number of perfect matching in a simple graph G with an
even number of vertices and degree sequence d1,d2,...,dn is at most
∏i=1n(di!)2di1. This bound is sharp if and only if
G is a union of complete balanced bipartite graphs.