×

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

MSC:

05C40 Connectivity

Citations:

Zbl 0638.00009