The minimum size of a graph with given tree connectivity (Q2227103)

The paper under review investigates generalizations of connectivity, where a path between two vertices is changed to a tree containing some \(k\) vertices. Given a graph \(G\) a set of vertices \(S\subseteq V(G)\), let \( \kappa_G(S)\) denote the maximum number of trees, which are (1) subgraphs of \(G\), (2) pairwise edge-disjoint, (3) the common vertices of any two of the trees is exactly \(S\). (Such trees are called internally disjoint.) Similarly, let \( \lambda_G(S)\) denote the maximum number of trees, which are (1) subgraphs of \(G\), (2) pairwise edge-disjoint. (Such trees are called edge-disjoint.) Let \(\kappa_k(G)\) and \(\lambda_k(G)\) defined as \(\kappa_k(G) =\min \{ \kappa_G(S) : S\subseteq V(G), |S|=k\}\) and \(\lambda_k(G) =\min \{ \lambda_G(S) : S\subseteq V(G), |S|=k\}\). Let \(f(n, k, t)\) (\(g(n, k, t)\)) be the minimum size of a connected graph \(G\) with order \(n\) and \(\kappa_k(G) = t\) (\(\lambda_k(G) = t\)), where \(3 \leq k \leq n\) and \(1 \leq t \leq n-\lceil k/2\rceil\). When \(t\) is arbitrary, the paper obtains upper bounds of both \(f(n, k, t)\) and \(g(n, k, t)\) for \(k =3, 4, 5\), and shows that these bounds can be attained. When \(k\) is arbitrary, the paper obtains an upper bound of \(g(n, k, t)\) for \(t =1, 2, 3, 4\) and an upper bound of \(f(n, k, t)\) for \(t =1, 2, 3\). These bounds can also be attained.