authors
- REYES GUILLERMO, ROSALIO
- RODRIGUEZ GARCIA, JOSE MANUEL
- SIGARRETA ALMIRA, JOSE MARIA
- VILLETA LOPEZ, MARIA DEL CARMEN
On the hyperbolicity constant of circular-arc graphs
Articles
Overview
published in
- DISCRETE APPLIED MATHEMATICS Journal
publication date
- June 2019
start page
- 244
end page
- 256
volume
- 263
Digital Object Identifier (DOI)
International Standard Serial Number (ISSN)
- 0166-218X
Electronic International Standard Serial Number (EISSN)
- 1872-6771
abstract
- Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.
Classification
subjects
- Mathematics
keywords
- circular graphs; circular-arc graphs<, geometric graphs; gromov hyperbolicity; geodesics