A note on distance approximating trees in graphs

Let G = (V, E) be a connected graph endowed with the standard graph-metric d(G) and in which longest induced simple cycle has length lambda(G). We prove that there exists a tree T = (V, F) such that \d(G)(u, upsilon) - d(T)(u, upsilon)\ less than or equal to left perpendicular lambda(G)/2 right perpendicular + alpha for all vertices u, upsilon is an element of V, where alpha = 1 if lambda(G) not equal 4, 5 and alpha = 2 otherwise. The case lambda(G) = 3 (i.e., G is a chordal graph) has been considered in Brandstadt, Chepoi, and Dragan, (1999) J.Algorithms 30. The proof contains an efficient algorithm for determining such a tree T. (C) 2000 Academic Press.