On Steiner centers and Steiner medians of graphs

✍ Scribed by Oellermann, Ortrud R.

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 143 KB
• Volume: 34
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199912)34:4<258::aid-net4>3.0.co;2-2

✦ Synopsis

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 Յ n Յ ͉V(G)͉, the Steiner n-eccentricity e n (v) of v is defined as e n (v) ϭ max{d(S)͉ S ʕ V(G), ͉S͉ ϭ n, and v ʦ S}. The Steiner n-radius rad n G and Steiner n-diameter diam n G are defined as the minimum and maximum n-eccentricity respectively, taken over all vertices of G. Relationships between rad n G and diam n G 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 rad n G 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) ϭ ¥{d(S)͉v ʦ 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.