Premium
The average Steiner distance of a graph
Author(s) -
Dankelmann Peter,
Oellermann Ortrud R.,
Swart Henda C.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199605)22:1<15::aid-jgt3>3.0.co;2-o
Subject(s) - combinatorics , mathematics , steiner tree problem , graph , connectivity , discrete mathematics
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. © 1996 John Wiley & Sons, Inc.