Matching and edge-connectivity in graphs with given maximum degree

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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 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.

Original languageEnglish
Article number112438
JournalDiscrete Mathematics
Volume344
Issue number8
Number of pages18
ISSN0012-365X
DOIs
Publication statusPublished - Aug 2021

Bibliographical note

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

  • Edge-connectivity
  • Matching number
  • Maximum degree

Fingerprint

Dive into the research topics of 'Matching and edge-connectivity in graphs with given maximum degree'. Together they form a unique fingerprint.

Cite this