{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T22:30:55Z","timestamp":1769207455510,"version":"3.49.0"},"reference-count":54,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2017,9,24]],"date-time":"2017-09-24T00:00:00Z","timestamp":1506211200000},"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>A graph is chordal if every induced cycle has exactly three edges. A vertex separator set in a graph is a set of vertices that disconnects two vertices. A graph is    \u03b4   -hyperbolic if every geodesic triangle is    \u03b4   -thin. In this paper, we study the relation between vertex separator sets, certain chordality properties that generalize being chordal and the hyperbolicity of the graph. We also give a characterization of being quasi-isometric to a tree in terms of chordality and prove that this condition also characterizes being hyperbolic, when restricted to triangles, and having stable geodesics, when restricted to bigons.<\/jats:p>","DOI":"10.3390\/sym9100199","type":"journal-article","created":{"date-parts":[[2017,9,26]],"date-time":"2017-09-26T04:28:01Z","timestamp":1506400081000},"page":"199","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Generalized Chordality, Vertex Separators and Hyperbolicity on Graphs"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1344-6189","authenticated-orcid":false,"given":"\u00c1lvaro","family":"Mart\u00ednez-P\u00e9rez","sequence":"first","affiliation":[{"name":"Department of Economic analysis and Finances, Universidad de Castilla-La Mancha, Avda. Real F\u00e1brica de Sedas s\/n, 45600 Talavera de la Reina, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,9,24]]},"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","doi-asserted-by":"crossref","unstructured":"Bridson, M., and Haefliger, A. (1999). Metric Spaces of Non-Positive Curvature, Springer.","DOI":"10.1007\/978-3-662-12494-9"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Burago, D., Burago, Y., and Ivanov, S. (2001). A course in metric geometry. Graduate Studies in Mathematics, AMS.","DOI":"10.1090\/gsm\/033"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Buyalo, S., and Schroeder, V. (2007). Elements of Asymptotic Geometry. EMS Monographs in Mathematics, European Mathematical Society.","DOI":"10.4171\/036"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Gyhs, E., and de la Harpe, P. (1990). Sur le groupes hyperboliques d\u2019apr\u00e8s Mikhael Gromov. Progress in Math, Birkh\u00e4user.","DOI":"10.1007\/978-1-4684-9167-8"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.exmath.2005.01.010","article-title":"Gromov hyperbolic spaces","volume":"23","year":"2005","journal-title":"Expos. Math."},{"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","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_9","doi-asserted-by":"crossref","first-page":"# P67","DOI":"10.37236\/2175","article-title":"Distortion of the hyperbolicity constant of a graph","volume":"19","author":"Carballosa","year":"2012","journal-title":"Electron. J. Comb."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"# P210","DOI":"10.37236\/697","article-title":"Gromov hyperbolicity of line graphs","volume":"18","author":"Carballosa","year":"2011","journal-title":"Electron. J. Comb."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1016\/j.disc.2013.04.009","article-title":"Gromov hyperbolic graphs","volume":"313","author":"Bermudo","year":"2013","journal-title":"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":"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. Dedicata"},{"key":"ref_14","first-page":"1137","article-title":"Gromov hyperbolicity of the jG and \n        \n          \n            \n\t\t\t\n\t\t\t\n              \u0237\n\t\t\t  \u02dc\n              \n              G\n\t\t\t  \n            \n          \n        \n       metrics","volume":"134","year":"2006","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_15","first-page":"43","article-title":"Hyperbolicity and parameters of graphs","volume":"100","author":"Michel","year":"2011","journal-title":"Ars Comb."},{"key":"ref_16","first-page":"1141","article-title":"Gromov hyperbolic cubic graphs","volume":"10","author":"Pestana","year":"2012","journal-title":"Cent. Eur. J. Math."},{"key":"ref_17","first-page":"193","article-title":"Gromov hyperbolic tessellation graphs","volume":"97","author":"Portilla","year":"2015","journal-title":"Util. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF02921869","article-title":"Gromov hyperbolicity through decomposition of metric spaces II","volume":"14","author":"Portilla","year":"2004","journal-title":"J. Geom. Anal."},{"key":"ref_19","first-page":"77","article-title":"Stability of Gromov hyperbolicity","volume":"2","author":"Portilla","year":"2009","journal-title":"J. Adv. Math. Stud."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"83","DOI":"10.5565\/PUBLMAT_53109_04","article-title":"A characterization of Gromov hyperbolicity of surfaces with variable negative curvature","volume":"53","author":"Portilla","year":"2009","journal-title":"Publ. Matorsz."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s12044-012-0060-0","article-title":"Bounds on Gromov hyperbolicity constant in graphs","volume":"122","author":"Sigarreta","year":"2012","journal-title":"Proc. Indian Acad. Sci. Math. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1897","DOI":"10.1080\/00207160.2013.866232","article-title":"Computing the hyperbolicity constant of a cubic graph","volume":"91","author":"Sigarreta","year":"2014","journal-title":"Int. J. Comput. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.disc.2010.11.005","article-title":"On the hyperbolicity constant in graphs","volume":"311","author":"Sigarreta","year":"2011","journal-title":"Discret. Math."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/s12044-013-0149-0","article-title":"Hyperbolicity in median graphs","volume":"123","author":"Sigarreta","year":"2013","journal-title":"Proc. Indian Acad. Sci. Math. Sci."},{"key":"ref_25","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_26","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.dam.2003.01.003","article-title":"\u0394 additive and \u0394 ultra-additive maps, Gromov\u2019s trees, and the Farris transform","volume":"146","author":"Dress","year":"2005","journal-title":"Discret. Appl. Math."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1006\/eujc.1996.0015","article-title":"T-theory: An overview","volume":"17","author":"Dress","year":"1996","journal-title":"Eur. J. Comb."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1038\/nature06830","article-title":"Hierarchical structure and the prediction of missing links in networks","volume":"453","author":"Clauset","year":"2008","journal-title":"Nature"},{"key":"ref_29","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_30","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_31","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. Model."},{"key":"ref_32","first-page":"45","article-title":"Contr\u00f4le du traffic sur les r\u00e9seaux \u00e0 g\u00e9om\u00e9trie hyperbolique\u2014Vers 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_33","first-page":"976","article-title":"Geometry of network security","volume":"2","author":"Jonckheere","year":"2004","journal-title":"Proc. Am. Control Conf."},{"key":"ref_34","first-page":"1","article-title":"Euclidean versus hyperbolic congestion in idealized versus experimental networks","volume":"7","author":"Jonckheere","year":"2011","journal-title":"Int. Math."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(98)00123-1","article-title":"Minimal vertex separators of chordal graphs","volume":"89","year":"1998","journal-title":"Discret. Appl. Math."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_1","article-title":"An introduction to chordal graphs and clique trees, Graph Theory and Sparse Matrix Multiplication","volume":"Volume 56","author":"Blair","year":"1993","journal-title":"IMA Volumes in Mathematics and its Applications"},{"key":"ref_37","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_38","doi-asserted-by":"crossref","first-page":"# P43","DOI":"10.37236\/530","article-title":"Hyperbolicity and chordality of a graph","volume":"18","author":"Wu","year":"2011","journal-title":"Electron. J. Comb."},{"key":"ref_39","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_40","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_41","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","article-title":"On rigid circuit graphs","volume":"25","author":"Dirac","year":"1961","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"2865","DOI":"10.1016\/j.disc.2013.08.032","article-title":"A Dirac-type Characterization of k-chordal Graphs","volume":"313","author":"Krithika","year":"2013","journal-title":"Discret. Math."},{"key":"ref_43","first-page":"2293","article-title":"High-dimensional Gaussian graphical model selection: Walk summability and local separation criterion","volume":"13","author":"Anandkumar","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1147","DOI":"10.2140\/gt.2005.9.1147","article-title":"Geometry of pseudocharacters","volume":"9","author":"Manning","year":"2005","journal-title":"Geom. Topol."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10240-014-0067-4","article-title":"Constructing group actions on quasi-trees and applications to mapping class groups","volume":"122","author":"Bestvina","year":"2015","journal-title":"Publ. Math. l\u2019IH\u00c9S"},{"key":"ref_46","first-page":"335","article-title":"A Geometric Proof of the Structure Theorem for Cyclic Splittings of Free Groups","volume":"50","author":"Cashen","year":"2017","journal-title":"Topol. Proc."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"525","DOI":"10.5186\/aasfm.2012.3734","article-title":"Real-valued functions and metric spaces quasi-isometric to trees","volume":"37","year":"2012","journal-title":"Ann. Acad. Sci. Fenn. Math."},{"key":"ref_48","first-page":"53","article-title":"Gromov hyperbolicity through decomposition of metric spaces","volume":"103","year":"2004","journal-title":"Acta Math. Hung."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00229-011-0463-8","article-title":"Quasi-isometries between visual hyperbolic spaces","volume":"137","year":"2012","journal-title":"Manuscr. Math."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1142\/S0219199700000232","article-title":"Cheeger isoperimetric constants of Gromov-hyperbolic spaces with quasi-pole","volume":"4","author":"Cao","year":"2000","journal-title":"Commun. Contemp. Math."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Mart\u00ednez-P\u00e9rez, A., and Rodr\u00edguez, J.M. (2017). Cheeger isoperimetric constant of Gromov hyperbolic manifolds and graphs. Commun. Contemp. Math., in press.","DOI":"10.1142\/S021919971750050X"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1112\/plms\/pdw018","article-title":"Limit sets for modules over groups on CAT(0) spaces: From the Euclidean to the hyperbolic","volume":"112","author":"Bieri","year":"2016","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.aim.2003.11.008","article-title":"Trees and ultrametric spaces: A categorical equivalence","volume":"189","author":"Hughes","year":"2004","journal-title":"Adv. Math."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s00209-008-0431-5","article-title":"Uniformly continuous maps between ends of \u211d-trees","volume":"263","year":"2009","journal-title":"Math. Z."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/10\/199\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:45:47Z","timestamp":1760208347000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/10\/199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,24]]},"references-count":54,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2017,10]]}},"alternative-id":["sym9100199"],"URL":"https:\/\/doi.org\/10.3390\/sym9100199","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,24]]}}}