×

On Steiner centers and Steiner medians of graphs. (English) Zbl 0968.05027

Summary: Let \(G\) be connected graph and \(S\) a set of vertices of \(G\). Then a Steiner tree for \(S\) is a connected subgraph of \(G\) of smallest size (number of edges) that contains \(S\). The size of such a subgraph is called the Steiner distance for \(S\) and is denoted by \(d(S)\). For a vertex \(v\) of \(G\), and integer \(n\), \(2\leq n\leq |V(G)|\), the Steiner \(n\)-eccentricity \(e_n(v)\) of \(v\) is defined as \(e_n(v)= \max\{d(S)\mid S\subseteq V(G)\), \(|S|= n\), and \(v\in S\}\). The Steiner \(n\)-radius \(\text{rad}_nG\) and Steiner \(n\)-diameter \(\text{diam}_nG\) are defined as the minimum and maximum \(n\)-eccentricity respectively, taken over all vertices of \(G\). Relationships between \(\text{rad}_nG\) and \(\text{diam}_nG\) are given if \(G\) is a tree and a conjecture (with some supporting results) is made that relates these parameters for general graphs. The subgraph induced by these vertices with \(n\)-eccentricity \(\text{rad}_nG\) is called the Steiner \(n\)-center of \(G\) and is denoted by \(C_n(G)\). It is shown that every graph is the Steiner \(n\)-center of some graph. The Steiner \(n\)-distance of a vertex \(v\), denoted by \(d_n(v)\), is defined by \(d_n(v)= \sum\{d(S)\mid v\in S\), \(|S|= n\}\). The Steiner \(n\)-median \(M_n(G)\) of \(G\) is the subgraph induced by those vertices with minimum Steiner \(n\)-distance. Algorithms for finding \(C_n(T)\) and \(M_n(T)\) for a tree \(T\) are described. It is shown that the distance between the \(C_n(T)\) and \(M_n(T)\) for a tree \(T\) can be arbitrarily large. Eccentricity measures are defined that extend those of the Steiner \(n\)-eccentricity and Steiner \(n\)-distance of a vertex. Then it is shown that every vertex on a shortest path between the Steiner \(n\)-center and Steiner \(n\)-median of a tree belongs to a “center” relative to one of these eccentricity measures.

MSC:

05C12 Distance in graphs
90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beineke, Discr Appl Math 68 pp 249– (1996) · Zbl 0858.05033
[2] Buckley, J Graph Theory 5 pp 427– (1981) · Zbl 0449.05056
[3] and Applied and algorithmic graph theory, McGraw-Hill, New York, 1993.
[4] Chartrand, ??asopis Pro P??stování Matematiky 114 pp 399– (1989)
[5] Dankelmann, J Graph Theory 22 pp 15– (1996) · Zbl 0849.05026
[6] and Computers and intractability: A guide to NP-completeness, Freeman, New York, 1979. · Zbl 0411.68039
[7] Hendry, J Graph Theory 9 pp 477– (1985)
[8] Henning, ARS Comb 29C pp 13– (1990)
[9] A note on graphs with distant center and median, Recent studies in graph theory, (Editor), Vishwa, 1989.
[10] Jordan, J Reine Angew Math 70 pp 185– (1869) · JFM 02.0344.01
[11] Miller, ARS Comb 15 pp 179– (1983)
[12] Oellermann, J Graph Theory 20 pp 113– (1995) · Zbl 0834.05024
[13] and Steiner n-eccentricity sequences of graphs, Recent studies in graph theory, (Editor), Vishwa, Gulbarga, 1989.
[14] Oellermann, J Graph Theory 14 pp 585– (1990) · Zbl 0721.05035
[15] Slater, J Graph Theory 2 pp 209– (1978) · Zbl 0425.05021
[16] Slater, J Graph Theory 4 pp 389– (1980) · Zbl 0446.05029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.