Eccentricity-approximating trees in chordal graphs
The eccentricity of a vertex \(v\) of a graph is the maximum distance of \(v\) to any other vertex in the graph. A spanning tree \(T\) of a connected graph \(G\) is called eccentricity \(k\)-approximating when for every vertex \(v\), the difference of the eccentricity of \(v\) in \(T\) and the eccentricity of \(v\) in \(G\) is at most \(k\). This paper shows that every chordal graph has an eccentricity 2-approximating spanning tree.
scientific article; zbMATH DE number 1462289