On the minimum size of graphs with given generalized connectivity (Q6559394)

The connectivity \(\kappa(G)\) of a connected graph \(G\) is the minimum number of vertices of \(G\) whose removal disconnects \(G\). By a theorem of \textit{H. Whitney} [Am. J. Math. 54, 150--168 (1932; Zbl 0003.32804)], \N\[\N\kappa(G)=\min_{(u,v)}\left\{\kappa_G(u,v)\right\} \N\]\Nwhere the minimum is over the pairs \((u,v)\) of vertices of \(G\) and \(\kappa_G(u,v)\) denotes the maximum number of paths between \(u\) and \(v\) in \(G\) such that any two of these paths do not share a vertex other than \(u\) or \(v\).\N\N\textit{M. Hager} [J. Comb. Theory, Ser. B 38, 179--189 (1985; Zbl 0566.05041)] generalized \(\kappa(G)\) as follows: for any set \(S\) of vertices of \(G\), denote by \(\kappa_G(S)\) the maximum number of trees in \(G\) such that any two of these trees do not share an edge and the intersection of their vertex sets is \(S\). The generalized \(k\)-connectivity \(\kappa_k(G)\) of \(G\) is then defined in the spirit of the above equality as \N\[\N\kappa_k(G)=\min_S\left\{\kappa_G(S)\right\} \N\]\Nwhere the minimum is over the sets \(S\) of \(k\) vertices of \(G\).\N\NIn this article, the smallest possible number of edges \(f(n,k,t)\) of a connected graph \(G\) with \(n\) vertices and generalized \(k\)-connectivity \(t\) is investigated. It is shown that, if \(k\) is at least \(4\) and \(t\) at most \(n-\lfloor{k/2}\rfloor\), then \N\[\Nf(n,k,t)\geq\left\lceil\frac{t(t+2)}{2t+2}n\right\rceil.\N\]\NIt is also shown that, when \(k\) is equal to \(4\) and \(t\) to \(2\), this inequality is sharp. This improves on a bound of \textit{Y. Sun} et al. [Discuss. Math. Graph Theory 41, No. 2, 409--425 (2021; Zbl 1459.05045)] whereby \N\[ \Nf(n,k,t)\geq\left\lceil\frac{t(t+1)}{2t+1}n\right\rceil \N\]\Nwhen \(k\) is at least \(3\) and \(t\) at most \(n-\lfloor{k/2}\rfloor\) which, by a result of \textit{S. Li} et al. [Australas. J. Comb. 51, 209--220 (2011; Zbl 1233.05120)] is sharp when \(k\) is equal to \(3\), \(t\) is equal to \(2\), and \(n\) is not \(9\) or \(10\).