2022/11/18 by Alexandr Kostochka, Douglas B. West, Kostochka, Alexandr V. +3 · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2211.10427
openalex publication_date 2022/11/18 · openalex created_date 2022/11/28 · openalex updated_date 2026/07/28
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≥ r and is [r+n(k-r)]∏i=1n-1(r-i) when n