The average connectivity of a graph
type: Item
instance of: scholarly article
title: The average connectivity of a graph
zbMATH Open document ID: 1002.05040
DOI: 10.1016/S0012-365X(01)00180-7
author: L. W. Beineke
author: Ortrud R. Oellermann
author: Raymond E. Pippert
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1792414
zbMATH Keywords: average connectivity
zbMATH Keywords: uniformly connected
reviewed by: Mark E. Watkins
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00180-7
OpenAlex ID: W2048460015
Recommended article: Average connectivity and average edge-connectivity in graphs
Recommended article: Average edge-connectivity of a graph
Recommended article: The average connectivity of a digraph
Recommended article: Bounds on the average connectivity of a graph
Recommended article: The average lower connectivity of graphs
Recommended article: Average distance and vertex-connectivity
Recommended article: Q4645486
Recommended article: Q3567781
Recommended article: The average size of a connected vertex set of a \(k\)-connected graph
Recommended article: The maximum average connectivity among all orientations of a graph
description: scientific article; zbMATH DE number 1792414