The maximum number of perfect matchings in graphs with a given degree sequence
type: Item
instance of: scholarly article
title: The maximum number of perfect matchings in graphs with a given degree sequence
zbMATH Open document ID: 1183.05064
author: Noga Alon
author: S. Friedland
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://arxiv.org/abs/0803.2578
full work available at URL: https://eudml.org/doc/117197
full work available at URL: v15i1n13.html
review text: Summary: We show that the number of perfect matchings in a simple graph \(G\) with an even number of vertices and degree sequence \(d_1,d_2, \dots ,d_n\) is at most \(\pi_{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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 5540875
zbMATH Keywords: perfect matchings
zbMATH Keywords: permanents
zbMATH Keywords: complete balanced bipartite graphs
MaRDI profile type: Publication
arXiv ID: 0803.2578
description: scientific article