Menu
For an integer \(\ell \geq 2\), the \(\ell\)-connectivity (\(\ell\)-edge-connectivity) of a graph \(G\) of order \(p\) is the minimum number of vertices (edges) that need to be deleted from \(G\) to produce a disconnected graph with at least \(\ell\) components or a graph with at most \(\ell-1\) vertices. Let \(G\) be a graph of order \(p\) and \(\ell\)-connectivity \(\kappa_\ell\). For each \(k \in \{0,1,\ldots,\kappa_\ell\}\), let \(s_k\) be the minimum \(\ell\)-edge-connectivity among all graphs obtained from \(G\) by deleting \(k\) vertices from \(G\). Then \(f_\ell = \{(0, s_0), \ldots, (\kappa_\ell, s_{\kappa_\ell})\}\) is the \(\ell\)-connectivity function of \(G\). The \(\ell\)-connectivity functions of complete multipartite graphs and caterpillars are determined.