The Steiner \(k\)-eccentricity on trees (Q2232615)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Steiner \(k\)-eccentricity on trees |
scientific article |
Statements
The Steiner \(k\)-eccentricity on trees (English)
0 references
6 October 2021
0 references
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\).
0 references
Steiner distance
0 references
Steiner tree
0 references
Steiner eccentricity
0 references
graph algorithms
0 references