The maximum number of perfect matchings in graphs with a given degree sequence

Noga Alon, Shmuel Friedland

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

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 languageEnglish (US)
Article numberN13
JournalElectronic Journal of Combinatorics
Volume15
Issue number1 N
DOIs
StatePublished - Apr 24 2008
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'The maximum number of perfect matchings in graphs with a given degree sequence'. Together they form a unique fingerprint.

Cite this