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’\) are internally disjoint if \(V(T) \cap V(T’) = S\) and \(E(T) \cap E(T’) = \emptyset\). 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 \(\min_{S \subseteq V(G), |S|=k} \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.