Matching and edge-connectivity in graphs with given maximum degree

Michael A. Henning*, Anders Yeo

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

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

OriginalsprogEngelsk
Artikelnummer112438
TidsskriftDiscrete Mathematics
Vol/bind344
Udgave nummer8
Antal sider18
ISSN0012-365X
DOI
StatusUdgivet - 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.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Matching and edge-connectivity in graphs with given maximum degree'. Sammen danner de et unikt fingeraftryk.

Citationsformater