Sharp bounds for the generalized connectivity ${\kappa }_3(G)$

Abstract

Let $G$ be a nontrivial connected graph of order $n$ and let $k$ be an integer with $2\le k\le n$. For a set $S$ of $k$ vertices of $G$, let $\kappa (S)$ denote the maximum number $\ell$ of edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for every pair $i,j$ of distinct integers with $1\le i,j\le \ell$. A collection $\{T_1,T_2,...,T_{\ell }\}$ of trees in $G$ with this property is called an internally disjoint set of trees connecting $S$. Chartrand et al. generalized the concept of connectivity as follows: The $k$-$connectivity$, denoted by ${\kappa }_k(G)$, of $G$ is defined by ${\kappa }_k(G)=$min$\{\kappa (S)\}$, where the minimum is taken over all $k$-subsets $S$ of $V(G)$. Thus ${\kappa }_2(G)=\kappa (G)$, where $\kappa (G)$ is the connectivity of $G$. In general, the investigation of ${\kappa }_k(G)$ is very difficult. We therefore focus on the investigation on ${\kappa }_3(G)$ in this paper. We study the relation between the connectivity and the 3-connectivity of a graph. First we give sharp upper and lower bounds of ${\kappa }_3(G)$ for general graphs $G$, and construct two kinds of graphs which attain the upper and lower bound, respectively. We then show that if $G$ is a connected planar graph, then $\kappa (G)-1\le {\kappa }_3(G)\le \kappa (G)$, and give some classes of graphs which attain the bounds. In the end we show that the problem whether $\kappa (G)={\kappa }_3(G)$ for a planar graph $G$ can be solved in polynomial time.

18 pages