## Abstract

The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μ_{n}(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μ_{n}(G) ≤ μ_{k}(G) + μ_{n+1-k}(G) where 2 ≤ k ≤ n - 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n - 1, it is shown that μ_{n}(T) ≤ (n/k)μ_{k}(T) and the range for μ_{n}(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined.

Original language | English |
---|---|

Pages (from-to) | 15-22 |

Number of pages | 8 |

Journal | Journal of Graph Theory |

Volume | 22 |

Issue number | 1 |

DOIs | |

Publication status | Published - May 1996 |

Externally published | Yes |

## ASJC Scopus subject areas

- Geometry and Topology