On the Hyperbolicity of Chordal Graphs

Gunnar Brinkmann^{1}, Jack H. Koolen^{1}, and V. Moulton^{2}

{gunnar, jkoolen}@mathematik.uni-bielefeld.de

vince@dirac.fmi.mh.se

Annals of Combinatorics 5(1) p.61-69 March, 2001

Abstract:

The hyperbolicity
of a metric space in Gromov's sense can be viewed as a measure of how "tree-like"
the space is, since those spaces for which
holds are precisely the set of (metric) trees. Here, we show that any chordal
graph equipped with the usual graph metric is in this sense reasonably
tree-like. In particular, we prove that the hyperbolicity of any chordal
graph is bounded, and is at most two. Moreover, we characterize those chordal
graphs with hyperbolicity one.

References:

1. R. Anstee and M. Farber, On bridged graphs and cop-win graphs, J. Combin. Theory Ser. B 44 (1988) 22每28.

2. H.-J. Bandelt and H. Mulder, Distance-hereditary graphs, J. Combin. Theory Ser. B 41 (1986) 182每208.

3. H. Bodlaender, T. Kloks, and D. Kratsch, Treewidth and pathwidth of permutation graphs, SIAM J. Discrete Math. 8 No. 4 (1995) 606每616.

4. B. Bowditch, Notes on Gromov's hyperbolicity criterion for path metric spaces, In: Group Theory from a Geometric Viewpoint, E. Ghys et al., Eds., World Scientific, 1991, pp. 64每 167.

5. P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archeological and Historical Sciences, F. Hodson et al., Eds., Edinburgh University Press, 1971, pp. 387-395.

6. A. Dress, V. Moulton, and W. Terhalle, T-theory: an overview, Europ. J. Combin. 17 (1996) 161每175.

7. Group Theory Form a Geometric Viewpoint, E. Ghys, A. Haefliger, and A. Verjovsky, Eds., World Scientific, 1991.

8. M. Gromov, Hyperbolic Groups, Essays in Group Theory, MSRI Series Vol. 8, S.Gersten, Ed., Springer-Verlag, 1988.

9. J. Koolen and V. Moulton, Hyperbolic bridged graphs, preprint.

10. D. Neumann and M. Shapiro, A Short Course in Geometric Group Theory, Lecture Notes for the ANU Workshop Jan./Feb., 1996.

11. T. McKee and F. McMorris, Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, 1999.

12. V. Moulton and M. Steel, Retractions of finite distance functions onto tree metrics, Discrete Appl. Math. 91 (1999) 215每233.

13. K. Zaretsky, Reconstruction of a tree from the distances between its pendant vertices, Uspekhi Math. Nauk (Russian Mathematical Surveys) 20 (1965) 90每92 (in Russian).