A Note on Distance Approximating Trees in Graphs

Let G = (V, E) be a connected graph endowed with the standard graph-metric dGand in which longest induced simple cycle has lengthλ (G). We prove that there exists a tree T = (V,F ) such that| dG(u, v) − dT(u, v)| ≤ ⌊λ(G)2⌋ + αfor all vertices u, v ∈ V, whereα = 1 if λ(G) ≠ = 4, 5 and α = 2 otherwise. The case λ(G) = 3 (i.e., G is a chordal graph) has been considered in Brandstädt, Chepoi, and Dragan, (1999) J.Algorithms 30. The proof contains an efficient algorithm for determining such a treeT .