On the Hyperbolicity of Edge-Chordal and Path-Chordal Graphs

If X is a geodesic metric space and x1, x2, x3 ∈ X, ageodesic triangleT = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is δ-hyperbolic(in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the other two sides, for every...

Full description

Saved in:
Bibliographic Details
Published in:Filomat 2016-01, Vol.30 (9), p.2599-2607
Main Authors: Bermudo, Sergio, Carballosa, Walter, Rodríguez, José M., Sigarreta, José M.
Format: Article
Language:English
Subjects:
College mathematics
Graph theory
Vertices
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:If X is a geodesic metric space and x1, x2, x3 ∈ X, ageodesic triangleT = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is δ-hyperbolic(in the Gromov sense) if any side of T is contained in a δ-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 propertywith 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.
ISSN:0354-5180
2406-0933
DOI:10.2298/FIL1609599B