Henning, Michael A.; Oellermann, Ortrud R.; Swart, Henda C. On vertices with maximum Steiner eccentricity in graphs. (English) Zbl 0735.05035 Graph theory, combinatorics, algorithms, and applications, Proc. 2nd Int. Conf., San Francisco/CA (USA) 1989, 393-403 (1991). Summary: [For the entire collection see Zbl 0734.00014.]Let \(G\) be a connected graph and \(S\) a nonempty set of vertices of \(G\). Then the Steiner distance of \(S\) is the minimum size of a connected subgraph whose vertex set contains \(S\). For a connected graph \(G\) with \(p\) vertices and an integer \(n\) \((2\leq n\leq p)\), the Steiner \(n\)-eccentricity of a vertex \(v\) of \(G\) is the maximum Steiner distance among all sets \(S\) of \(n\) vertices of \(G\) with \(v\in S\). The Steiner \(n\)-diameter \(\text{diam}_ nG\) of \(G\) is the maximum Steiner \(n\)-eccentricity of all its vertices and the Steiner \(n\)-periphery is the subgraph induced by those vertices with maximum Steiner \(n\)-eccentricity. Graphs that are Steiner \(n\)-peripheries of graphs are characterized. It is shown, for an integer \(n\geq 3\), that the Steiner \((n-1)\)-periphery of a tree is contained in its Steiner \(n\)-periphery, but that this containment does not hold for graphs in general. For a graph \(G\) and an integer \(n\geq 3\) it is verified that \(\text{diam}_ nG\leq (n+1)/(n-1)\text{diam}_{n-1}G\). Further, this bound is shown to be best possible. Cited in 1 Document MSC: 05C12 Distance in graphs 05C35 Extremal problems in graph theory Keywords:Steiner distance; maximum Steiner \(n\)-eccentricity Citations:Zbl 0734.00014 PDFBibTeX XMLCite \textit{M. A. Henning} et al., in: Existence theorems for nonseparable \(\alpha\)-valuations of snakes. . 393--403 (1991; Zbl 0735.05035)