Oellermann, Ortrud R. A note on the \(\ell\)-connectivity function of a graph. (English) Zbl 0656.05043 Combinatorics, graph theory, and computing, Proc. 18th Southeast. Conf., Boca Raton/Fl. 1987, Congr. Numerantium 60, 181-188 (1987). [For the entire collection see Zbl 0638.00009.] The j-connectivity \(K_ j(G)\) (respectively, j-edge-connectivity \(\lambda_ j(G))\) is the minimum number of vertices (respectively, edges) whose removal produces a graph with at least j components or with fewer than j vertices. If \(k\in \{0,1,2,...,K_ j(G)\}\) let \(s_ k\) be the minimum j-edge-connectivity among all subgraphs obtained by removing k vertices from G. The j-connectivity function \(f_ j\) of G is defined by \(f_ j(k)=s_ k\) for \(0\leq k\leq K_ j(G).\) Several properties of the j-connectivity function are presented. In particular, for any graph G and integer \(j\geq 3\), the j-connectivity function \(f_ j\) is nonincreasing. And if f is a decreasing function from \(\{\) 0,1,...,K\(\}\) to the nonnegative integers such that \(f(K)=0\), then f is the j-connectivity function of some graph. Reviewer: P.J.Slater Cited in 1 Document MSC: 05C40 Connectivity Keywords:j-connectivity function Citations:Zbl 0638.00009 PDFBibTeX XML