## Abstrakt

In a recent paper (2018) [10] 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 a_{k,λ}, b_{k,λ} and c_{k,λ} (depending only on k and λ) such that α^{′}(G)≥a_{k,λ}⋅n+b_{k,λ}⋅m−c_{k,λ}. We prove that the above bounds are tight for essentially all densities of graphs.

Originalsprog | Engelsk |
---|---|

Artikelnummer | 112438 |

Tidsskrift | Discrete Mathematics |

Vol/bind | 344 |

Udgave nummer | 8 |

Antal sider | 18 |

ISSN | 0012-365X |

DOI | |

Status | Udgivet - aug. 2021 |

### Bibliografisk note

Funding Information:Research supported in part by the University of Johannesburg.Research of the first author support in part by the University of Johannesburg. Research of the second author supported by the Danish research council under grant number DFF-7014-00037B.

Funding Information:

Research of the first author support in part by the University of Johannesburg . Research of the second author supported by the Danish research council under grant number DFF-7014-00037B .

Publisher Copyright:

© 2021 Elsevier B.V.