{
  "id": "1112.0127",
  "version": "v3",
  "published": "2011-12-01T10:10:49.000Z",
  "updated": "2013-05-14T09:17:02.000Z",
  "title": "On the generalized (edge-)connectivity of graphs",
  "authors": [
    "Xueliang Li",
    "Yaping Mao",
    "Yuefang Sun"
  ],
  "comment": "15 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The generalized $k$-connectivity $\\kappa_k(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of generalized $k$-edge-connectivity $\\lambda_k(G)$. For general $k$, the generalized $k$-edge-connectivity of a complete graph is obtained. For $k\\geq 3$, tight upper and lower bounds of $\\kappa_k(G)$ and $\\lambda_k(G)$ are given for a connected graph $G$ of order $n$, that is, $1\\leq \\kappa_k(G)\\leq n-\\lceil\\frac{k}{2}\\rceil$ and $1\\leq \\lambda_k(G)\\leq n-\\lceil\\frac{k}{2}\\rceil$. Graphs of order $n$ such that $\\kappa_k(G)=n-\\lceil\\frac{k}{2}\\rceil$ and $\\lambda_k(G)=n-\\lceil\\frac{k}{2}\\rceil$ are characterized, respectively. Nordhaus-Gaddum-type results for the generalized $k$-connectivity are also obtained. For $k=3$, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of $\\lambda_3(G)$ for a graph $G$ in terms of the edge-connectivity $\\lambda$ of $G$ are obtained, that is, $\\frac{3\\lambda-2}{4}\\leq \\lambda_3(G)\\leq \\lambda$, and two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain that $\\lambda(G)-1\\leq \\lambda_3(G)\\leq \\lambda(G)$ if $G$ is a connected planar graph, and the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-05-14T09:17:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C40",
      "05C05",
      "05C75",
      "05C76"
    ],
    "keywords": [
      "lower bounds",
      "edge-connectivity",
      "nordhaus-gaddum-type results",
      "complete graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.0127L"
    }
  }
}