## Abstract

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 language | English |
---|---|

Pages (from-to) | 204-212 |

Number of pages | 9 |

Journal | Discrete Applied Mathematics |

Volume | 143 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 30 Sept 2004 |

Externally published | Yes |

## Keywords

- Bounds
- Minimum average distance
- Oriented graphs

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics