Minimum average distance of strong orientations of graphs

Peter Dankelmann, Ortrud R. Oellermann, Jian Liang Wu

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


The average distance of a graph (strong digraph) G, denoted by μ(G) is the average, among the distances between all pairs (ordered pairs) of vertices of G. If G is a 2-edge-connected graph, then μ→(G) is the minimum average distance taken over all strong orientations of G. A lower bound for μ→(G) in terms of the order, size, girth and average distance of G is established and shown to be sharp for several complete multipartite graphs. It is shown that there is no upper bound for μ→(G) in terms of μ(G). However, if every edge of G lies on 3-cycle, then it is shown that μ→(G) ≤ 7÷4μ(G). This bound is improved for maximal planar graphs to 5÷3μ(G) and even further to 5÷3μ(G) for eulerian maximal planar graphs and for outerplanar graphs with the property that every edge lies on 3-cycle. In the last case the bound is shown to be sharp.

Original languageEnglish
Pages (from-to)204-212
Number of pages9
JournalDiscrete Applied Mathematics
Issue number1-3
Publication statusPublished - 30 Sept 2004
Externally publishedYes


  • Bounds
  • Minimum average distance
  • Oriented graphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Minimum average distance of strong orientations of graphs'. Together they form a unique fingerprint.

Cite this