On the minimum size of graphs with given generalized connectivity

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)], \[ \kappa(G)=\min_{(u,v)}\left\{\kappa_G(u,v)\right\} \] where 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\). \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 \[ \kappa_k(G)=\min_S\left\{\kappa_G(S)\right\} \] where the minimum is over the sets \(S\) of \(k\) vertices of \(G\). In 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 \[ f(n,k,t)\geq\left\lceil\frac{t(t+2)}{2t+2}n\right\rceil. \] It 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 \[ f(n,k,t)\geq\left\lceil\frac{t(t+1)}{2t+1}n\right\rceil \] when \(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\).

Recommendations

Cites work

This page was built for publication: On the minimum size of graphs with given generalized connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6559394)