On the average Steiner distance of graphs with presribed properties
type: Item
instance of: scholarly article
title: On the average Steiner distance of graphs with presribed properties
zbMATH Open document ID: 0884.05040
DOI: 10.1016/S0166-218X(97)00035-8
author: Peter Dankelmann
author: H. C. Swart
author: Ortrud R. Oellermann
published in: Discrete Applied Mathematics
publication date: 1998-01-07T00:00:00Z
full work available at URL: dam
review text: 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.
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1088856
zbMATH Keywords: Steiner distance
zbMATH Keywords: chromatic number
zbMATH Keywords: bounds
MaRDI profile type: Publication
cites work: Steiner distance in graphs
cites work: The average distance and the independence number
cites work: Average distance and domination number
cites work: The average Steiner distance of a graph
cites work: Minimally 2-connected graphs.
cites work: Mean distance in a graph
cites work: Distance in graphs
cites work: Edge-vulnerability and mean distance
cites work: Q3351388
cites work: Q3880849
cites work: On the sum of all distances in a graph or digraph
cites work: On Minimal Blocks
cites work: ON DISTANCES IN CHROMATIC GRAPHS
cites work: Q5606538
description: scientific article; zbMATH DE number 1088856