Dankelmann, Peter; Oellermann, Ortrud R.; Swart, Henda C. The average Steiner distance of a graph. (English) Zbl 0849.05026 J. Graph Theory 22, No. 1, 15-22 (1996). Let \(G= (V,E)\) be a graph and let \(S\) be a subset of vertices. The Steiner distance for \(S\) is the number of edges in a smallest connected subgraph of \(G\) containing \(S\). If \(S\) consists of two vertices, the Steiner distance for \(S\) is just the distance between these vertices. The parameter \(\mu_n(G)\) is defined to be the mean of the Steiner distances over all \(n\)-element subsets of \(G\). The authors extend several of the results already known for \(\mu_2(G)\). For example, they prove: Theorem 2.2. Let \(G\) be connected weighted graph and \(2\leq k\leq n- 1\). Then \(\mu_n(G)\leq \mu_k(G)+ \mu_{n+ 1- k}(G)\). Theorem 3.1. Let \(T\) be a tree of order \(p\geq n\) and \(2\leq k\leq n- 1\). Then \(\mu_n(T)\leq {n\over k} \mu_k(T)\). Furthermore, equality holds if and only if \(T\) is a star. Reviewer: J.E.Graver (Syracuse) Cited in 1 ReviewCited in 27 Documents MSC: 05C12 Distance in graphs 05C05 Trees Keywords:Steiner distance; tree; star PDFBibTeX XMLCite \textit{P. Dankelmann} et al., J. Graph Theory 22, No. 1, 15--22 (1996; Zbl 0849.05026) Full Text: DOI