Note on the Generalized Connectivity

Abstract

For a vertex set $S$ with cardinality at least $2$ in a graph $G$, a tree connecting $S$, known as a Steiner tree or $S$-tree, is required. Two $S$-trees $T$ and $T^{\prime }$ are internally disjoint if $V(T)\cap V(T^{\prime })=S$ and $E(T)\cap E(T^{\prime })=\mathrm{\varnothing }$. Let ${\kappa }_G(G)$ denote the maximum number of internally disjoint Steiner trees connecting $S$ in $G$. The generalized $k$-connectivity ${\kappa }_k(G)$ of $G$, introduced by Chartrand et al., is defined as $\underset{S\subseteq V(G),|S|=k}{min}{\kappa }_G(S)$. This paper establishes a sharp upper bound for generalized $k$-connectivity. Furthermore, graphs of order $n$ with ${\kappa }_3(G)=n-2,n-3$ are characterized.