Abstract
We study the minimum number of maximum matchings in a bipartite multigraph (Formula presented.) with parts (Formula presented.) and (Formula presented.) under various conditions, refining the well-known lower bound due to M. Hall. When (Formula presented.), every vertex in (Formula presented.) has degree at least (Formula presented.), and every vertex in (Formula presented.) has at least (Formula presented.) distinct neighbors, the minimum is (Formula presented.) when (Formula presented.) and is (Formula presented.) when (Formula presented.). When every vertex has at least two neighbors and (Formula presented.), the minimum is (Formula presented.), where (Formula presented.). We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions.
Original language | English (US) |
---|---|
Pages (from-to) | 525-555 |
Number of pages | 31 |
Journal | Journal of Graph Theory |
Volume | 106 |
Issue number | 3 |
DOIs | |
State | Published - Jul 2024 |
Keywords
- Hall's theorem
- bipartite
- maximum matching
- multigraph
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics