<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 1" %>
On the Hyperbolicity of Chordal Graphs
Gunnar Brinkmann1, Jack H. Koolen1, and V. Moulton2
1FSPM-Strukturbildungsprozesse, University of Bielefeld, D-33501 Bielefeld, Germany
{gunnar, jkoolen}@mathematik.uni-bielefeld.de
2Physics and Mathematics Department (FMI), Mid Sweden University, Sundsvall, S 851-70, Sweden
vince@dirac.fmi.mh.se
Annals of Combinatorics 5(1) p.61-69 March, 2001
AMS Subject Classification: 05C12, 05C05, 05C10, 05C75
Abstract:
The hyperbolicity $ \delta^* \ge 0$ 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 $ \delta^* = 0$ 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.
Keywords: chordal graphs, block graphs, bridged graphs, four-point condition, hyperbolicity, $ \delta$-hyperbolic

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).