Options
Tight bounds for the vertices of degree k in minimally k-connected graphs
Publikationstyp
Journal Article
Date Issued
2018-05
Sprache
English
Author(s)
TORE-URI
Journal
Volume
88
Issue
1
Start Page
146
End Page
153
Citation
Journal of Graph Theory (2018)
Publisher DOI
Scopus ID
For minimally k-connected graphs on n vertices, Mader proved a tight lower bound for the number |Vk| of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if m : |E| is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long-standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case.
Subjects
lower bounds
minimally k-connected graphs
tight
vertices of degree k
DDC Class
510: Mathematik