{
  "id": "1603.09281",
  "version": "v1",
  "published": "2016-03-30T17:17:57.000Z",
  "updated": "2016-03-30T17:17:57.000Z",
  "title": "A Tight Bound for Minimal Connectivity",
  "authors": [
    "Jens M. Schmidt"
  ],
  "comment": "4 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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 Oxley's bound is best possible. We show that this is not the case, but propose a closely related bound that deviates from 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-30T17:17:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "tight bound",
      "minimal connectivity",
      "bound contains maders bound",
      "tight lower bound",
      "special case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}