Sharp lower bounds for the number of maximum matchings in bipartite multigraphs

Alexandr V. Kostochka, Douglas B. West, Zimu Xiang

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)525-555
Number of pages31
JournalJournal of Graph Theory
Volume106
Issue number3
DOIs
StatePublished - Jul 2024

Keywords

  • Hall's theorem
  • bipartite
  • maximum matching
  • multigraph

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Sharp lower bounds for the number of maximum matchings in bipartite multigraphs'. Together they form a unique fingerprint.

Cite this