



























We study the minimum number of maximum matchings in a bipartite multigraph G with parts $X$ and $Y$ under various conditions, refining the well-known lower bound due to M. Hall. When $|X|=n$, every vertex in $X$ has degree at least $k$, and every vertex in $X$ has at least $r$ distinct neighbors, the minimum is $r!(k-r+1)$ when $n\ge r$ and is $[r+n(k-r)]\prod_{i=1}^{n-1}(r-i)$ when $n<r$. When every vertex has at least two neighbors and $|Y|-|X|=t\ge 0$, the minimum is $[(n-1)t+2+b](t+1)$, where $b=|E(G)|-2(n+t)$. We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。