In a recent paper (2018)  the authors determine tight lower bounds on the matching number in a graph with given maximum degree in terms of the number of vertices (order) and number of edges (size). In this paper, we raise the problem to a higher level by proving a tight lower bound on the matching number of a graph with given maximum degree and edge-connectivity in terms of its order and size. For a graph G of order n, size m, matching number α′(G), edge-connectivity λ(G)≥λ≥2 and maximum degree k≥λ we determine best possible constants ak,λ, bk,λ and ck,λ (depending only on k and λ) such that α′(G)≥ak,λ⋅n+bk,λ⋅m−ck,λ. We prove that the above bounds are tight for essentially all densities of graphs.
Bibliographical notePublisher Copyright:
© 2021 Elsevier B.V.
- Matching number
- Maximum degree