paper

Graphs with large generalized 3-connectivity

arXiv:1201.2983

Abstract

Let $S$ be a nonempty set of vertices of a connected graph $G$ . A collection $T_{1}, ..., T_{ℓ}$ 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 $I^º_{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, $I^º_{2} (G)$ is the connectivity of $G$ . In this paper, sharp upper and lower bounds of $I^º_{3} (G)$ are given for a connected graph $G$ of order $n$ , that is, $1 \leq I^º_{3} (G) \leq n - 2$ . Graphs of order $n$ such that $I^º_{3} (G) = n - 2, n - 3$ are characterized, respectively.

9 pages