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

Simple item page
dc.creatorAlon, Noga
dc.creatorFriedland, Shmuel
dc.date2008-03-18
dc.date2008-05-26
dc.date.accessioned2026-07-07T09:40:35Z
dc.date.available2026-07-07T09:40:35Z
dc.descriptionWe show that the number of perfect matching in a simple graph $G$ with an even number of vertices and degree sequence $d_1,d_2, ..., d_n$ is at most $\prod_{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.
dc.description2 pages
dc.identifierhttps://arxiv.org/abs/0803.2578
dc.identifierhttp://arxiv.org/abs/0803.2578
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/161531
dc.subjectCombinatorics
dc.subject05A15, 05C70
dc.titleThe maximum number of perfect matchings in graphs with a given degree sequence
dc.typetext

Files

Collections

arXiv