The Steiner \(k\)-eccentricity on trees (Q2232615)

The paper is devoted to a linear algorithm computing the Steiner \(k\)-eccentricity of a vertex in a tree and estimates of the upper and lower bounds of the average \(k\)-eccentricity on trees. The distance between two vertices on a graph \(G=(V(G),E(G))\) is the length of a shortest path between them, the Steiner distance \[d_G(S)=\min\{|E(T)| ; T \text{ is a subtree of } G,\ S \subseteq V(T)\}\] of a subset \(S \subset V(G)\), \(|S| \geq 2\). For any \(k\geq 2\), the Steiner \(k\)-eccentricity \(\operatorname{ecc}_k(v,G)\) of a vertex \(v\in V(G)\) is the maximal Steiner distance \(d_G(S)\) of the sets \(S\subseteq V(G)\), \(|S|= k\), containing \(v\), and, by definition, \(\operatorname{ecc}_1(v,G):= 0\). If \(S\subseteq V(G)\) with \(|S|=k\) is a maximum set, i.e., \(d_G(S) = \operatorname{ecc}_k(v,G)\), then \(S\) is a Steiner \(k\)-eccentricity \(v\)-set. A minimum Steiner tree is a Steiner \(k\)-eccentricity \(v\)-tree corresponding to the \(k\)-set \(S\). Finally, the average Steiner \(k\)-eccentricity of a graph \(G\) is the average value \(\operatorname{aecc}_k(G) := \frac{1}{|V(G)|}\sum_{v\in V(G)} \operatorname{ecc}_k(v,G)\). In the paper the authors propose linear algorithms for recursively calculating the Steiner \(k\)-eccentricity of a given vertex in a tree (Algorithm 1), for the longest paths (Algorithm 2), and for path shrinking (Algorithm 3). The main results are Theorem 2.6, stating the linear running time \(O(kn)\), and Theorem 3.3, stating the estimates of the average eccentricity for \(k\geq 3\) and \(T\) a tree of order \(n >k\), \(k-\frac{1}{n} < \operatorname{aecc}_k(T) \leq n-1\).