Mathematical Properties on the Hyperbolicity of Interval Graphs

Abstract

Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. In particular, we are interested in interval and indifference graphs, which are important classes of intersection and Euclidean graphs, respectively. Interval graphs (with a very weak hypothesis) and indifference graphs are hyperbolic. In this paper, we give a sharp bound for their hyperbolicity constants. The main result in this paper is the study of the hyperbolicity constant of every interval graph with edges of length 1. Moreover, we obtain sharp estimates for the hyperbolicity constant of the complement of any interval graph with edges of length 1.

Keywords

• interval graphs
• indifference graphs
• euclidean graphs
• geometric graphs
• Gromov hyperbolicity
• geodesics