The average connectivity of a digraph
type: Item
instance of: scholarly article
title: The average connectivity of a digraph
zbMATH Open document ID: 1047.05024
author: Michael A. Henning
author: Ortrud R. Oellermann
published in: Discrete Applied Mathematics
publication date: 2004-08-06T00:00:00Z
review text: In the papers of \textit{L. W. Beineke, O. R. Oellermann} and \textit{R. E. Pippert} [Discrete Math. 252, 31-45 (2002; Zbl 1002.05040)] and \textit{P. Dankelmann} and \textit{O. R. Oellermann} [Discrete Appl. Math. 129, 305-318 (2003; Zbl 1021.05062)] the concept of average connectivity in a graph has been studied. In this paper this concept is considered in digraphs. For two distinct vertices \(u\) and \(v\) of a digraph \(D\), let \(\kappa_D(u,v)\) denote the connectivity from \(u\) to \(v\), the maximum number of internally disjoint directed paths from \(u\) to \(v\) in \(D\). Thus the connectivity \(\kappa(D)=\min\{\kappa_D(u,v)\mid u,v\in V(D)\}\). The average connectivity of \(D\), \(\overline{\kappa}(D)\), is the average connectivity from \(u\) to \(v\) over all ordered pairs \((u,v)\) of distinct vertices of \(D\). Sharp bounds are given on \(\overline{\kappa}(D)\) of orientations \(D\) of graphs in terms of their orders and sizes. These results are improved further for complete graphs (giving tournaments) and trees. It is proved that \(\overline{\kappa}_{\max}(T)\), the maximum average connectivity among all orientations of a tree \(T\), lies in the interval (2/9, 1/2] and a polynomial time procedure for finding \(\overline{\kappa}_{\max}(T)\) is suggested. The authors note that their results hold also for the average arc-connectivity of a digraph (defined as expected).
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2083774
zbMATH Keywords: average connectivity
zbMATH Keywords: oriented graphs
zbMATH Keywords: oriented trees
zbMATH Keywords: tournaments
MaRDI profile type: Publication
full work available at URL: j.dam.2003.04.003
OpenAlex ID: W2047797996
cites work: On the Steiner median of a tree
cites work: The average connectivity of a graph
cites work: Bounds on the average connectivity of a graph
cites work: Q4198056
cites work: On the sum of all distances in a graph or digraph
DOI: 10.1016/J.DAM.2003.04.003
Recommended article: The average connectivity of regular multipartite tournaments
Recommended article: Bounds on the average connectivity of a graph
Recommended article: The maximum average connectivity among all orientations of a graph
Recommended article: The average connectivity of a graph
Recommended article: Minimum average distance of strong orientations of graphs
Recommended article: The average size of a connected vertex set of a \(k\)-connected graph
Recommended article: Average Distance and Edge-Connectivity I
Recommended article: Q4826169
Recommended article: Average distance in graphs with removed elements
Recommended article: Average distance and domination number revisited
description: scientific article; zbMATH DE number 2083774