Premium
From steiner centers to steiner medians
Author(s) -
Oellermann Ortrud R.
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200202
Subject(s) - combinatorics , steiner tree problem , mathematics , vertex (graph theory) , steiner system , vertex connectivity , connectivity , graph , discrete mathematics
The Steiner distance of set S of vertices in a connected graph G is the minimum number of edges in a connected subgraph of G containing S . For n ≥ 2, the Steiner n ‐eccentricity e n ( v ) of a vertex v of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contain v . The Steiner n‐center of G is the subgraph induced by those vertices of G having minimum n ‐eccentricity. The Steiner n ‐distance of a vertex v of G is defined as. The Steiner n ‐median of G is the subgraph of G induced by the vertices of G of minimum Steiner n ‐distance. Known algorithms for finding the Steiner n ‐centers and Steiner n ‐medians of trees are used to show that the distance between the Steiner n ‐centre and Steiner n ‐median of a tree can be arbitrarily large. Centrality measures that allow every vertex on a shortest path from the Steiner n ‐center to the Steiner n ‐median of a tree to belong to the “center” with respect to one of these measures are introduced and several proeprties of these centrality measures are established. © 1995 John Wiley & Sons, Inc.