On the Hyperbolicity of Edge-Chordal and Path-Chordal Graphs Articles uri icon

publication date

  • January 2016

start page

  • 2599

end page

  • 2607

issue

  • 30

volume

  • 30

international standard serial number (ISSN)

  • 0354-5180

electronic international standard serial number (EISSN)

  • 2406-0933

abstract

  • También publicado en ArXiv.org: arXiv:1201.1717 [cs.SI]. Abstract: If X is a geodesic metric space and x(1), x(2), x(3) is an element of X, a geodesic triangle T = {x(1), x(2), x(3)} is the union of the three geodesics [x(1)x(2)], [x(2)x(3)] and [x(3)x(1)] in X. The space X is delta-hyperbolic (in the Gromov sense) if any side of T is contained in a delta-neighborhood of the union of the other two sides, for every geodesic triangle T in X. An important problem in the study of hyperbolic graphs is to relate the hyperbolicity with some classical properties in graph theory. In this paper we find a very close connection between hyperbolicity and chordality: we extend the classical definition of chordality in two ways, edge-chordality and path-chordality, in order to relate this property with Gromov hyperbolicity. In fact, we prove that every edge-chordal graph is hyperbolic and that every hyperbolic graph is path-chordal. Furthermore, we prove that every path-chordal cubic graph with small path-chordality constant is hyperbolic.

keywords

  • infinite graphs; chordal graphs; gromov hyperbolicity; cubic graphs; gromov-hyperbolicity; constant