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

Noga Alon; Shmuel Friedland

doi:10.37236/888

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

Noga Alon, Shmuel Friedland

Research output: Contribution to journal › Article › peer-review

36 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 d₁, d₂,..., d_n is at most ∏_i=1ⁿ(d_i· !)^1/2d_i. 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	https://doi.org/10.37236/888
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

Access to Document

10.37236/888

Cite this

@article{5842ee0e20d64ed1be5f4c11a82b49c6,

title = "The maximum number of perfect matchings in graphs with a given degree sequence",

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.",

keywords = "Perfect matchings, Permanents",

author = "Noga Alon and Shmuel Friedland",

year = "2008",

month = apr,

day = "24",

doi = "10.37236/888",

language = "English (US)",

volume = "15",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1 N",

}

TY - JOUR

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

AU - Alon, Noga

AU - Friedland, Shmuel

PY - 2008/4/24

Y1 - 2008/4/24

N2 - 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.

AB - 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.

KW - Perfect matchings

KW - Permanents

UR - https://www.scopus.com/pages/publications/43849090347

UR - https://www.scopus.com/inward/citedby.url?scp=43849090347&partnerID=8YFLogxK

U2 - 10.37236/888

DO - 10.37236/888

M3 - Article

AN - SCOPUS:43849090347

SN - 1077-8926

VL - 15

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1 N

M1 - N13

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this