On the $\ell$-Connectivity Function of Caterpillars and Complete Multipartite Graphs

Abstract

For an integer $\ell \ge 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,\dots ,{\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),\dots ,({\kappa }_{\ell },s_{{\kappa }_{\ell }})\}$ is the $\ell$-connectivity function of $G$. The $\ell$-connectivity functions of complete multipartite graphs and caterpillars are determined.