On the average Steiner distance of graphs with presribed properties (Q1372733): Difference between revisions

The Steiner distance of a set \(S\) of vertices in a connected graph \(G\), \(d_G(S)\), is the number of edges in a smallest Steiner tree for \(S\). The average Steiner distance \(\mu _n(G)\) of \(G\) is the average of the Steiner distances of all \(n\)-subsets of \(V(G)\). The authors also define the \(n\)-diameter, \(n\)-radius and further notions related to distances in such a way that \(n=2\) corresponds to the standard notions. Generalizing several results on the average distance (see \textit{R. C. Entringer, D. E. Jackson} and \textit{D. A. Snyder} [Czech. Math. J. 26(101), 283-296 (1976; Zbl 0329.05112)], \textit{J. Plesník} [J. Graph Theory 8, 1-21 (1984; Zbl 0552.05048)] and \textit{I. Tomescu} and \textit{R. A. Melter} [Q. J. Math., Oxf. II. Ser. 40, No. 160, 475-480 (1989; Zbl 0702.05034)]), they give bounds on the average Steiner distance related to the \(n\)-diameter, the chromatic number, and others.