Steiner centers in graphs

Abstract

Abstract The Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n ‐eccentricity e n (ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n ‐diameter of G is the maximum n ‐eccentricity among the vertices of G while the n ‐radius of G is the minimum n ‐eccentricity. The n ‐center of G is the subgraph induced by those vertices of G having minimum n ‐eccentricity. It is shown that every graph is the n ‐center of some graph. Several results on the n ‐center of a tree are established. In particular, it is shown that the n ‐center of a tree is a tree and those trees that are n ‐centers of trees are characterized.