The average connectivity of a digraph

Michael A. Henning; Ortrud R. Oellermann

doi:10.1016/j.dam.2003.04.003

The average connectivity of a digraph

Michael A. Henning, Ortrud R. Oellermann

Research output: Contribution to journal › Article › peer-review

17 Citations (Scopus)

Abstract

In this paper we consider the concept of the average connectivity of a digraph D defined to be the average, over all ordered pairs (u,v) of vertices of D, of the maximum number of internally disjoint directed u-v paths. We determine sharp bounds on the average connectivity of orientations of graphs in terms of the number of vertices and edges and for tournaments and orientations of trees in terms of their orders. An efficient procedure for finding the maximum average connectivity among all orientations of a tree is described and it is shown that this maximum is always greater than 29 and at most 12.

Original language	English
Pages (from-to)	143-153
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	140
Issue number	1-3
DOIs	https://doi.org/10.1016/j.dam.2003.04.003
Publication status	Published - 15 May 2004
Externally published	Yes

Keywords

Average connectivity
Oriented graphs
Oriented trees
Tournaments

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2003.04.003

Cite this

@article{8c320d23275e470a95615f14a4a212bc,

title = "The average connectivity of a digraph",

abstract = "In this paper we consider the concept of the average connectivity of a digraph D defined to be the average, over all ordered pairs (u,v) of vertices of D, of the maximum number of internally disjoint directed u-v paths. We determine sharp bounds on the average connectivity of orientations of graphs in terms of the number of vertices and edges and for tournaments and orientations of trees in terms of their orders. An efficient procedure for finding the maximum average connectivity among all orientations of a tree is described and it is shown that this maximum is always greater than 29 and at most 12.",

keywords = "Average connectivity, Oriented graphs, Oriented trees, Tournaments",

author = "Henning, {Michael A.} and Oellermann, {Ortrud R.}",

year = "2004",

month = may,

day = "15",

doi = "10.1016/j.dam.2003.04.003",

language = "English",

volume = "140",

pages = "143--153",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - The average connectivity of a digraph

AU - Henning, Michael A.

AU - Oellermann, Ortrud R.

PY - 2004/5/15

Y1 - 2004/5/15

N2 - In this paper we consider the concept of the average connectivity of a digraph D defined to be the average, over all ordered pairs (u,v) of vertices of D, of the maximum number of internally disjoint directed u-v paths. We determine sharp bounds on the average connectivity of orientations of graphs in terms of the number of vertices and edges and for tournaments and orientations of trees in terms of their orders. An efficient procedure for finding the maximum average connectivity among all orientations of a tree is described and it is shown that this maximum is always greater than 29 and at most 12.

AB - In this paper we consider the concept of the average connectivity of a digraph D defined to be the average, over all ordered pairs (u,v) of vertices of D, of the maximum number of internally disjoint directed u-v paths. We determine sharp bounds on the average connectivity of orientations of graphs in terms of the number of vertices and edges and for tournaments and orientations of trees in terms of their orders. An efficient procedure for finding the maximum average connectivity among all orientations of a tree is described and it is shown that this maximum is always greater than 29 and at most 12.

KW - Average connectivity

KW - Oriented graphs

KW - Oriented trees

KW - Tournaments

UR - http://www.scopus.com/inward/record.url?scp=2642526174&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2003.04.003

DO - 10.1016/j.dam.2003.04.003

M3 - Article

AN - SCOPUS:2642526174

SN - 0166-218X

VL - 140

SP - 143

EP - 153

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

The average connectivity of a digraph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this