Beineke, Lowell W.; Oellermann, Ortrud R.; Pippert, Raymond E. The average connectivity of a graph. (English) Zbl 1002.05040 Discrete Math. 252, No. 1-3, 31-45 (2002). For a graph \(G=(V,E)\) with \(u,v\in V\), let \(\kappa_G(u,v)\) denote the maximum number of internally disjoint \(uv\)-paths in \(G\). Thus \(\kappa(G):=\min\{\kappa_G(u,v):u,v\in V\}\). Define average connectivity of \(G\) to be \[ \overline{\kappa}(G)=\sum_{u,v\in V}\kappa_G(u,v)\Biggl/{|V|\choose 2}; \] it is computable in polynomial time. Upper bounds for \(\overline{\kappa}(G)\) are given in terms of the independence number, the degree sequence, and \(|V|\) and \(|E|\), respectively, this last bound being sharp. Theorem 3.1: If \(\overline{\kappa}(G)=\kappa(G)=k\), then \(k\geq 1\) implies \(\kappa(G-e)<k\) for all \(e\in E\), and \(k\geq 2\) implies \(\kappa(G-v)<k\) for all \(v\in V\). Three methods are given for constructing graphs satisfying the hypothesis of this theorem. Reviewer: Mark E.Watkins (Syracuse) Cited in 3 ReviewsCited in 21 Documents MSC: 05C40 Connectivity Keywords:average connectivity; uniformly connected PDFBibTeX XMLCite \textit{L. W. Beineke} et al., Discrete Math. 252, No. 1--3, 31--45 (2002; Zbl 1002.05040) Full Text: DOI