×

Steiner distance in graphs. (English) Zbl 0688.05040

Summary: For a nonempty set S of vertices of a connected graph G, the distance d(S) of S is the minimum size of a connected subgraph whose vertex set contains S. For integers n and p with \(2\leq n\leq p\), the minimum size of a graph G of order p is determined for which \(d(S)=n-1\) for all sets S of vertices of G having \(| S| =n\). For a connected graph G of order p and integer n with \(2\leq n\leq p\), the n-eccentricity of a vertex v of G is the maximum value of d(S) over all \(S\subseteq V(G)\) with v in S and \(| S| =n\). The minimum n-eccentricity \(rad_ nG\) is called the n-radius of G and the maximum n-eccentricity \(diam_ nG\) is its n- diameter. It is shown that \(diam_ nT\leq [n/(n-1)]rad_ nT\) for every tree T of order p with \(2\leq n\leq p\). For a graph G of order p the sequence \(diam_ 2G,diam_ 3G,...,diam_ pG\) is called the diameter sequence of G. In the case of trees, the n-radius and n-diameter are investigated and the diameter sequences of trees are characterized.

MSC:

05C35 Extremal problems in graph theory