The Average Steiner Distance of a Graph

Peter Dankelmann, Ortrud R. Oellermann, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

52 Citations (Scopus)

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 languageEnglish
Pages (from-to)15-22
Number of pages8
JournalJournal of Graph Theory
Volume22
Issue number1
DOIs
Publication statusPublished - May 1996
Externally publishedYes

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'The Average Steiner Distance of a Graph'. Together they form a unique fingerprint.

Cite this