{
  "id": "1201.2983",
  "version": "v1",
  "published": "2012-01-14T03:39:01.000Z",
  "updated": "2012-01-14T03:39:01.000Z",
  "title": "Graphs with large generalized 3-connectivity",
  "authors": [
    "Hengzhe Li",
    "Xueliang Li",
    "Yaping Mao",
    "Yuefang Sun"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $S$ be a nonempty set of vertices of a connected graph $G$. A collection $T_1,..., T_\\ell$ of trees in $G$ is said to be internally disjoint trees connecting $S$ if $E(T_i)\\cap E(T_j)= \\emptyset$ and $V(T_i)\\cap V(T_j)=S$ for any pair of distinct integers $i, j$, where $1 \\leq i, j \\leq r$. For an integer $k$ with $2 \\leq k \\leq n$, the generalized $k$-connectivity $\\kappa_k(G)$ of $G$ is the greatest positive integer $r$ such that $G$ contains at least $r$ internally disjoint trees connecting $S$ for any set $S$ of $k$ vertices of $G$. Obviously, $\\kappa_2(G)$ is the connectivity of $G$. In this paper, sharp upper and lower bounds of $\\kappa_3(G)$ are given for a connected graph $G$ of order $n$, that is, $1 \\leq \\kappa_3(G) \\leq n - 2$. Graphs of order $n$ such that $\\kappa_3(G) = n - 2, n - 3$ are characterized, respectively.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-01-14T03:39:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C40",
      "05C05"
    ],
    "keywords": [
      "internally disjoint trees connecting",
      "connected graph",
      "lower bounds",
      "sharp upper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1201.2983L"
    }
  }
}