×

Steiner distance in graphs with emphasis on eccentricity measures: A survey. (English) Zbl 0812.05020

The Steiner problem for weighted graphs is the graph analogue of the well-known Steiner problem in the Euclidean plane, namely: for a given connected weighted graph \(G\) and a subset \(S\) of the vertex set \(V(G)\) find a connected subgraph of smallest weight that contains \(S\). Such a subgraph is necessarily a tree called a Steiner tree for \(S\) and the weight of a Steiner tree is called the Steiner distance \(d(S)\) of \(S\).
Suppose that \(G\) has order \(p\), and let \(n\) be an integer with \(2\leq n\leq p\). Then the \(n\)-eccentricity \(e_ n(v)\) of a vertex \(v\) of \(G\) is defined by \(e_ n(v)= \text{Max}\{d(S): S\subseteq V(G)\), \(| S|= n\), and \(v\in S\}\), while the \(n\)-radius of \(G\) is defined by \(\text{rad}_ n(G)= \text{Min}\{e_ n(v): v\in V(G)\}\) and the \(n\)- diameter of \(G\) is defined by \(\text{diam}_ n(G)= \text{Max}\{e_ n(v): v\in V(G)\}\).
The paper gives a lot of results for these parameters. Particularly, for a connected graph \(G\) and an integer \(n\geq 3\) we have \(\text{diam}_ n(G)\leq (n+ 1)/(n- 1)\text{diam}_{n- 1}(G)\).
Additionally, centrality structures are considered. The Steiner \(n\)- center \(C_ n(G)\) of a graph \(G\) is the subgraph induced by the vertices \(v\) of \(G\) with \(e_ n(v)= \text{rad}_ n(G)\). An algorithm for finding the Steiner \(n\)-center of a tree is given. The Steiner \(n\)-distance of a vertex \(v\) in a connected graph \(G\) on \(p\geq n\) vertices is defined by \(d_ n(v)= \sum\{d(S): S\subseteq V(G)\), \(v\in S\), and \(| S|= n\}\). The Steiner \(n\)-median \(M_ n(G)\) of \(G\) is the subgraph induced by the vertices of minimum \(n\)-distance in \(G\). There is an algorithm to find the Steiner \(n\)-median of a tree and one to compute the \(n\)- distances of all vertices in a tree. The paper gives combinatorial properties of the Steiner \(n\)-center and the Steiner \(n\)-median of trees.

MSC:

05C12 Distance in graphs
05C35 Extremal problems in graph theory
05C05 Trees
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDFBibTeX XMLCite