{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:15:41Z","timestamp":1760242541828,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T00:00:00Z","timestamp":1509494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/sym9110255","type":"journal-article","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T16:01:19Z","timestamp":1509552079000},"page":"255","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Mathematical Properties on the Hyperbolicity of Interval Graphs"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1429-3644","authenticated-orcid":false,"given":"Juan C.","family":"Hern\u00e1ndez-G\u00f3mez","sequence":"first","affiliation":[{"name":"Faculty of Mathematics, Autonomous University of Guerrero, Carlos E. Adame 54, La Garita, Acapulco 39650, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rosal\u00edo","family":"Reyes","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Carlos III University of Madrid, Avenida de la Universidad 30, 28911 Legan\u00e9s, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2851-7442","authenticated-orcid":false,"given":"Jos\u00e9 M.","family":"Rodr\u00edguez","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Carlos III University of Madrid, Avenida de la Universidad 30, 28911 Legan\u00e9s, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 M.","family":"Sigarreta","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Carlos III University of Madrid, Avenida de la Universidad 30, 28911 Legan\u00e9s, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,11,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-1-4613-9586-7_3","article-title":"Hyperbolic groups","volume":"Volume 8","author":"Gersten","year":"1987","journal-title":"Essays in Group Theory"},{"key":"ref_2","unstructured":"Oshika, K. (2002). Discrete Groups, AMS Bookstore."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., and Lee, J.R. (2006, January 21\u201324). Algorithms on Negatively Curved Spaces. Proceedings of the Foundations of Computer Science (FOCS\u201906), Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2006.9"},{"key":"ref_4","first-page":"45","article-title":"Contr\u00f4le du traffic sur les r\u00e9seaux \u00e0 g\u00e9om\u00e9trie hyperbolique\u2013Vers une th\u00e9orie g\u00e9om\u00e9trique de la s\u00e9curit\u00e9 l\u2019acheminement de l\u2019information","volume":"8","author":"Jonckheere","year":"2002","journal-title":"J. Eur. Syst. Autom."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1016\/j.jmaa.2011.02.067","article-title":"Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces","volume":"380","year":"2011","journal-title":"J. Math. Anal. Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2599","DOI":"10.2298\/FIL1609599B","article-title":"On the Hyperbolicity of Edge-Chordal and Path-Chordal Graphs","volume":"30","author":"Bermudo","year":"2016","journal-title":"Filomat"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"3073","DOI":"10.1016\/j.disc.2016.06.013","article-title":"Small values of the hyperbolicity constant in graphs","volume":"339","author":"Bermudo","year":"2016","journal-title":"Discret. Math."},{"key":"ref_8","first-page":"1","article-title":"Sustaining the Internet with Hyperbolic Mapping","volume":"1","author":"Papadopoulos","year":"2010","journal-title":"Nature Commun."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00026-001-8007-7","article-title":"On the hyperbolicity of chordal graphs","volume":"5","author":"Brinkmann","year":"2001","journal-title":"Ann. Comb."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/s10474-016-0677-z","article-title":"Gromov hyperbolicity and convex tessellation graph","volume":"151","author":"Carballosa","year":"2017","journal-title":"Acta Math. Hungarica"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1987","DOI":"10.1137\/130941328","article-title":"Cop and Robber Game and Hyperbolicity","volume":"28","author":"Chalopin","year":"2014","journal-title":"SIAM J. Discret. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.endm.2008.06.046","article-title":"Notes on diameters, centers, and approximating trees of \u03b4-hyperbolic geodesic spaces and graphs","volume":"31","author":"Chepoi","year":"2008","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/s00453-010-9478-x","article-title":"Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs","volume":"62","author":"Chepoi","year":"2012","journal-title":"Algorithmica"},{"key":"ref_14","first-page":"18","article-title":"On computing the Gromov hyperbolicity","volume":"20","author":"Cohen","year":"2015","journal-title":"ACM J. Exp. Algortm."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1016\/j.ipl.2015.02.002","article-title":"Computing the Gromov hyperbolicity of a discrete metric space","volume":"115","author":"Fournier","year":"2015","journal-title":"J. Inf. Process. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s10711-009-9363-4","article-title":"Characterizing hyperbolic spaces and real trees","volume":"142","author":"Frigerio","year":"2009","journal-title":"Geom. Dedic."},{"key":"ref_17","first-page":"111","article-title":"Geometry of network security","volume":"6","author":"Jonckheere","year":"2004","journal-title":"Am. Control Conf."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.amc.2007.03.001","article-title":"Upper bound on scaled Gromov-hyperbolic delta","volume":"192","author":"Jonckheere","year":"2007","journal-title":"Appl. Math. Comput."},{"key":"ref_19","first-page":"157","article-title":"Scaled Gromov hyperbolic graphs","volume":"2","author":"Jonckheere","year":"2007","journal-title":"J. Graph Theory"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kiwi, M., and Mitsche, D. (2015). A Bound for the Diameter of Random Hyperbolic Graphs. ANALCO, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973761.3"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1006\/eujc.2002.0591","article-title":"Hyperbolic Bridged Graphs","volume":"23","author":"Koolen","year":"2002","journal-title":"Eur. J. Comb."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"036106","DOI":"10.1103\/PhysRevE.82.036106","article-title":"Hyperbolic geometry of complex networks","volume":"82","author":"Krioukov","year":"2010","journal-title":"Phys. Rev. E"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"P3.51","DOI":"10.37236\/5315","article-title":"Chordality properties and hyperbolicity on graphs","volume":"23","year":"2016","journal-title":"Electron. J. Comb."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Mart\u00ednez-P\u00e9rez, A. (2017). Generalized Chordality, Vertex Separators and Hyperbolicity on Graphs. Symmetry, 9.","DOI":"10.3390\/sym9100199"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"P2.39","DOI":"10.37236\/4053","article-title":"On the Hyperbolicity of Random Graphs","volume":"21","author":"Mitsche","year":"2014","journal-title":"Electron. J. Comb."},{"key":"ref_26","first-page":"1152","article-title":"Lack of Gromov-hyperbolicity in small-world networks","volume":"10","author":"Shang","year":"2012","journal-title":"Cent. Eur. J. Math."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1080\/15326349.2013.838510","article-title":"Non-hyperbolicity of random graphs with given expected degrees","volume":"29","author":"Shang","year":"2013","journal-title":"Stoch. Models"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"P43","DOI":"10.37236\/530","article-title":"Chordality and hyperbolicity of a graph","volume":"18","author":"Wu","year":"2011","journal-title":"Electron. J. Comb."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1213","DOI":"10.2969\/jmsj\/06731213","article-title":"Counting subgraphs in hyperbolic graphs with symmetry","volume":"67","author":"Calegari","year":"2015","journal-title":"J. Math. Soc. Jpn."},{"key":"ref_30","unstructured":"Eppstein, D. (2007). Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics."},{"key":"ref_31","unstructured":"Li, S., and Tucci, G.H. (arXiv, 2013). Traffic Congestion in Expanders, (p,\u03b4)-Hyperbolic Spaces and Product of Trees, arXiv."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Fishburn, P.C. (1985). Interval orders and interval graphs: A study of partially ordered sets. Wiley-Interscience Series in Discrete Mathematics, John Wiley and Sons.","DOI":"10.1016\/0012-365X(85)90042-1"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C. (1980). Algorithmic Graph Theory and Perfect Graphs, Academic Press.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","article-title":"A characterization of comparability graphs and of interval graphs","volume":"16","author":"Gilmore","year":"1964","journal-title":"Can. J. Math."},{"key":"ref_35","unstructured":"Cohen, J.E. (1978). Food webs and niche space. Monographs in Population Biology 11, Princeton University Press."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","article-title":"Finding Hamiltonian circuits in proper interval graphs","volume":"17","author":"Bertossi","year":"1983","journal-title":"Inf. Process. Lett."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","article-title":"A linear time recognition algorithm for proper interval graphs","volume":"87","author":"Panda","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.tcs.2015.03.012","article-title":"Spanning connectedness and Hamiltonian thickness of graphs and interval graphs","volume":"16","author":"Li","year":"2015","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/B:AMHU.0000028240.16521.9d","article-title":"Gromov hyperbolicity through decomposition of metric spaces","volume":"103","year":"2004","journal-title":"Acta Math. Hung."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"4592","DOI":"10.1016\/j.camwa.2011.10.041","article-title":"Computing the hyperbolicity constant","volume":"62","author":"Bermudo","year":"2011","journal-title":"Comput. Math. Appl."},{"key":"ref_41","first-page":"43","article-title":"Hyperbolicity and parameters of graphs","volume":"100","author":"Michel","year":"2011","journal-title":"Ars Comb."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/jgt.3190170112","article-title":"Extremal interval graphs","volume":"17","year":"1993","journal-title":"J. Graph Theory"},{"key":"ref_43","first-page":"1","article-title":"On the hyperbolicity constant of circulant networks","volume":"2015","author":"Sigarreta","year":"2015","journal-title":"Adv. Math. Phys."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/11\/255\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:49:10Z","timestamp":1760208550000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/11\/255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,1]]},"references-count":43,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2017,11]]}},"alternative-id":["sym9110255"],"URL":"https:\/\/doi.org\/10.3390\/sym9110255","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2017,11,1]]}}}