×

On the \(l\)-connectivity function of caterpillars and complete multipartite graphs. (English) Zbl 0760.05062

For a graph \(G\) and \(\ell\geq 2\) the \(\ell\)-connectivity \(\kappa_ \ell\) \((\ell\)-edge connectivity \(\lambda_ \ell)\) is the minimum number of vertices (edges) whose deletion results in a graph either with at least \(\ell\) components or with at most \(\ell-1\) vertices. Let \(0\leq k\leq\kappa_ \ell\) and \(G\) be either the complete multipartite graph or a caterpillar. In the paper the minimum \(\ell\)-edge-connectivity among all graphs obtained from \(G\) by deleting \(k\) vertices is determined.

MSC:

05C40 Connectivity
PDFBibTeX XMLCite