An upper bound for the number of perfect matchings in graphs

Simple item page
dc.creatorFriedland, Shmuel
dc.date2008-03-06
dc.date.accessioned2026-07-07T09:25:12Z
dc.date.available2026-07-07T09:25:12Z
dc.descriptionWe give an upper bound on the number of perfect matchings in an undirected simple graph $G$ with an even number of vertices, in terms of the degrees of all the vertices in $G$. This bound is sharp if $G$ is a union of complete bipartite graphs. This bound is a generalization of the upper bound on the number of perfect matchings in bipartite graphs on $n+n$ vertices given by the Bregman-Minc inequality for the permanents of $(0,1)$ matrices.
dc.description6 pages
dc.identifierhttps://arxiv.org/abs/0803.0864
dc.identifierhttp://arxiv.org/abs/0803.0864
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/156329
dc.subjectCombinatorics
dc.subjectHistory and Overview
dc.subject05A15, 05C70
dc.titleAn upper bound for the number of perfect matchings in graphs
dc.typetext

Files

Collections

arXiv