Abstract | ||
---|---|---|
For minimally $k$-connected graphs on $n$ vertices, Mader proved a tight lower bound for the number $|V_k|$ 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 Oxleyu0027s bound is best possible. show that this is not the case, but propose a closely related bound that deviates from Oxleyu0027s long-standing one only for small values of $m$. We prove that this new bound is best possible. The bound contains Maderu0027s bound as special case. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Combinatorics | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Upper and lower bounds,Mathematics,Special case |
DocType | Volume | Citations |
Journal | abs/1603.09281 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jens M. Schmidt | 1 | 0 | 1.69 |