{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:14:11Z","timestamp":1760242451884,"version":"build-2065373602"},"reference-count":60,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2017,7,27]],"date-time":"2017-07-27T00:00:00Z","timestamp":1501113600000},"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>Since the characterization of Gromov hyperbolic graphs seems a too ambitious task, there are many papers studying the hyperbolicity of several classes of graphs. In this paper, it is proven that every Mycielskian graph     G M     is hyperbolic and that     \u03b4 (  G M  )     is comparable to     diam (  G M  )    . Furthermore, we study the extremal problems of finding the smallest and largest hyperbolicity constants of such graphs; in fact, it is shown that     5 \/ 4 \u2264 \u03b4 (  G M  ) \u2264 5 \/ 2    . Graphs G whose Mycielskian have hyperbolicity constant     5 \/ 4     or     5 \/ 2     are characterized. The hyperbolicity constants of the Mycielskian of path, cycle, complete and complete bipartite graphs are calculated explicitly. Finally, information on     \u03b4 ( G )     just in terms of     \u03b4 (  G M  )     is obtained.<\/jats:p>","DOI":"10.3390\/sym9080131","type":"journal-article","created":{"date-parts":[[2017,7,27]],"date-time":"2017-07-27T11:28:40Z","timestamp":1501154920000},"page":"131","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Gromov Hyperbolicity in Mycielskian Graphs"],"prefix":"10.3390","volume":"9","author":[{"given":"Ana","family":"Granados","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Saint Louis University, Avenida del Valle 34, 28003 Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8334-0243","authenticated-orcid":false,"given":"Domingo","family":"Pestana","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911 Legan\u00e9s, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana","family":"Portilla","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Saint Louis University, Avenida del Valle 34, 28003 Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2851-7442","authenticated-orcid":false,"given":"Jos\u00e9","family":"Rodr\u00edguez","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911 Legan\u00e9s, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,7,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ghys, E., Haefliger, A., and Verjovsky, A. (1992). Notes on word hyperbolic groups. Group Theory from a Geometrical Viewpoint, World Scientific.","DOI":"10.1142\/9789814539746"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ghys, E., Haefliger, A., and Verjovsky, A. (1991). Notes on Gromov\u2019s hyperbolicity criterion for path-metric spaces. Group Theory from a Geometrical Viewpoint, Trieste, 1990, World Scientific.","DOI":"10.1142\/9789814539746"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ghys, E., and de la Harpe, P. (1990). Sur les Groupes Hyperboliques d\u2019apr\u00e8s Mikhael Gromov. Progress in Mathematics 83, Birkh\u00e4user Boston Inc.","DOI":"10.1007\/978-1-4684-9167-8"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gersten, S.M., and Publ, M.S.R.I. (1987). Hyperbolic Groups, in \u201cEssays in Group Theory\", Springer.","DOI":"10.1007\/978-1-4613-9586-7"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF00181569","article-title":"Quasi-geodesics segments and Gromov hyperbolic spaces","volume":"62","author":"Bonk","year":"1996","journal-title":"Geom. Dedicata"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1080\/15427951.2013.828336","article-title":"On the hyperbolicity of small-world and treelike random graphs","volume":"9","author":"Chen","year":"2013","journal-title":"Internet Math."},{"key":"ref_7","first-page":"157","article-title":"Scaled Gromov hyperbolic graphs","volume":"2","author":"Jonckheere","year":"2007","journal-title":"J. Graph Theory"},{"key":"ref_8","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_9","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_10","unstructured":"Oshika, K. (2002). Discrete Groups, AMS Bookstore, Iwanami Series on Modern Mathematics, Translations of Mathematical Monographs, Amer Mathematical Society."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/BF01444642","article-title":"Artin groups of finite type are biautomatic","volume":"292","author":"Charney","year":"1992","journal-title":"Math. Ann."},{"key":"ref_12","unstructured":"Edwards, K., Kennedy, W.S., and Saniee, I. (2016, April 25). Fast Approximation Algorithms for p-Centres in Large \u03b4-Hyperbolic Graphs. Available online: https:\/\/arxiv.org\/pdf\/1604.07359.pdf."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1109\/TNET.2007.899021","article-title":"On internet embedding in hyperbolic spaces for overlay construction and distance estimation","volume":"16","author":"Shavitt","year":"2008","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Verbeek, K., and Suri, S. (2014, January 8\u201311). Metric embeddings, hyperbolic space and social networks. Proceedings of the 30th Annual Symposium on Computational Geometry, Kyoto, Japan.","DOI":"10.1145\/2582112.2582139"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1002\/net.21631","article-title":"Metric tree-like structures in real-life networks: An empirical study","volume":"67","author":"Dragan","year":"2016","journal-title":"Networks"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Adcock, A.B., Sullivan, B.D., and Mahoney, M.W. (2013, January 7\u201310). Tree-like structure in large social and information networks. Proceedings of the 2013 IEEE 13th International Conference Data Mining (ICDM), Dallas, TX, USA.","DOI":"10.1109\/ICDM.2013.77"},{"key":"ref_17","unstructured":"Cohen, N., Coudert, D., and Lancin, A. (2012). Exact and Approximate Algorithms for Computing the Hyperbolicity of Large-Scale Graphs, INRIA. Rapport de Recherche RR-8074."},{"key":"ref_18","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_19","doi-asserted-by":"crossref","unstructured":"Montgolfier, F., Soto, M., and Viennot, L. (2011, January 25\u201327). Treewidth and Hyperbolicity of the Internet. Proceedings of the 2011 IEEE 10th International Symposium on Network Computing and Applications (NCA), Washington, DC, USA.","DOI":"10.1109\/NCA.2011.11"},{"key":"ref_20","first-page":"45","article-title":"Contr\u00f4le du trafic sur les r\u00e9seaux \u00e0 g\u00e9om\u00e9trie hyperbolique: Vers une th\u00e9orie g\u00e9om\u00e9trique de la s\u00e9curit\u00e9 de l\u2019acheminement de l\u2019information","volume":"8","author":"Jonckheere","year":"2002","journal-title":"J. Eur. Syst. Autom."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Jonckheere, E.A., and Lohsoonthorn, P. (July, January 30). Geometry of network security. Proceedings of the 2004 American Control Conference, Boston, MA, USA.","DOI":"10.23919\/ACC.2004.1386698"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., and Vax\u00e8s, Y. (2017, January 16\u201319). Core congestion is inherent in hyperbolic networks. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.149"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Grippo, E., and Jonckheere, E.A. (2016, January 19\u201322). Effective resistance criterion for negative curvature: application to congestion control. Proceedings of the IEEE Multi-Conference on Systems and Control, Buenos Aires, Argentina.","DOI":"10.1109\/CCA.2016.7587833"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1080\/15427951.2014.884513","article-title":"Traffic Congestion in Expanders, (p, \u03b4)-Hyperbolic Spaces and Product of Trees","volume":"11","author":"Li","year":"2015","journal-title":"Internet  Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/S0895480100380902","article-title":"1-Hyperbolic Graphs","volume":"16","author":"Bandelt","year":"2003","journal-title":"SIAM J. Discret. Math."},{"key":"ref_26","first-page":"18","article-title":"Sustaining the Internet with Hyperbolic Mapping","volume":"1","author":"Papadopoulos","year":"2010","journal-title":"Nat. Commun."},{"key":"ref_27","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_28","doi-asserted-by":"crossref","first-page":"210","DOI":"10.37236\/697","article-title":"Gromov hyperbolicity of line graphs","volume":"18","author":"Carballosa","year":"2011","journal-title":"Electr. J. Comb."},{"key":"ref_29","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":"Electr. Notes Discr. Math."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Diestel, R., and M\u00fcller, M. (2017). Connected tree-width. Combinatorica.","DOI":"10.1007\/s00493-016-3516-5"},{"key":"ref_31","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_32","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":"Europ. J. Comb."},{"key":"ref_33","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. Math. Sci."},{"key":"ref_34","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_35","doi-asserted-by":"crossref","first-page":"43","DOI":"10.37236\/530","article-title":"Chordality and hyperbolicity of a graph","volume":"18","author":"Wu","year":"2011","journal-title":"Electr. J. Comb."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1007\/s000140050138","article-title":"Gromov hyperbolicity and the Kobayashi metric on strictly pseudoconvex domains","volume":"75","author":"Balogh","year":"2000","journal-title":"Comment. Math. Helv."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s10240-003-0012-4","article-title":"Convexes hyperboliques et fonctions quasisym\u00e9triques","volume":"97","author":"Benoist","year":"2003","journal-title":"Publ. Math. Inst. Hautes \u00c9tudes Sci."},{"key":"ref_38","first-page":"73","article-title":"The Hilbert metric and Gromov hyperbolicity","volume":"48","author":"Karlsson","year":"2002","journal-title":"Enseign. Math."},{"key":"ref_39","first-page":"1137","article-title":"Gromov hyperbolicity of the jG and \n        \n          \n     \n          \n\t\t  \n      j\n      ~\n\t    \n\t      \n\t      G\n\t\n      \n        \n       metrics","volume":"134","year":"2006","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_40","first-page":"279","article-title":"Gromov hyperbolicity of certain conformal invariant metrics","volume":"32","year":"2007","journal-title":"Ann. Acad. Sci. Fenn. Math."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s00222-003-0287-6","article-title":"Geometric characterizations of Gromov hyperbolicity","volume":"153","author":"Balogh","year":"2003","journal-title":"Invent. Math."},{"key":"ref_42","unstructured":"Bonk, M., Heinonen, J., and Koskela, P. (2001). Uniformizing Gromov Hyperbolic Spaces, Ast\u00e9risque; Amer Mathematical Society."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1112\/blms\/bdp125","article-title":"Gromov hyperbolic equivalence of the hyperbolic and quasihyperbolic metrics in Denjoy domains","volume":"42","author":"Portilla","year":"2010","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref_44","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_45","first-page":"53","article-title":"Gromov hyperbolicity through decomposition of metric spaces","volume":"103","year":"2004","journal-title":"Acta Math. Hung."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s10114-005-0547-z","article-title":"Gromov hyperbolicity of Riemann surfaces","volume":"23","year":"2007","journal-title":"Acta Math. Sin."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","article-title":"Sur le coloriage des graphes","volume":"3","author":"Mycielski","year":"1955","journal-title":"Colloq. Math."},{"key":"ref_48","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. Inform. Proc. Lett."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1601","DOI":"10.1137\/140954787","article-title":"Recognition of C4-Free and 1\/2-Hyperbolic Graphs","volume":"28","author":"Coudert","year":"2014","journal-title":"SIAM J. Discret. Math."},{"key":"ref_50","first-page":"193","article-title":"An algorithm detecting hyperbolicity","volume":"Volume 25","author":"Papasoglu","year":"1996","journal-title":"Geometric and Computational Perspectives on Infinite Groups, DIMACS\u2014Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"1882","DOI":"10.1016\/j.aml.2011.05.011","article-title":"Hyperbolicity and complement of graphs","volume":"24","author":"Bermudo","year":"2011","journal-title":"Appl. Math. Lett."},{"key":"ref_52","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_53","unstructured":"Carballosa, W., de la Cruz, A., and Rodr\u00edguez, J.M. (2015, June 19). Gromov Hyperbolicity in Lexicographic Product Graphs. Available online: http:\/\/gama.uc3m.es\/index.php\/jomaro.html."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.1007\/s00010-014-0324-0","article-title":"Hyperbolicity in the corona and join of graphs","volume":"89","author":"Carballosa","year":"2015","journal-title":"Aequ. Math."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.dam.2016.06.017","article-title":"On the hyperbolicity of bipartite graphs and intersection graphs","volume":"214","author":"Coudert","year":"2016","journal-title":"Discret. App. Math."},{"key":"ref_56","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":"Electr. J. Comb."},{"key":"ref_57","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_58","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0012-365X(01)00115-7","article-title":"Graph homotopy and Graham homotopy","volume":"241","author":"Chen","year":"2001","journal-title":"Discret. Math."},{"key":"ref_59","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":"Discr. Math."},{"key":"ref_60","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":"Comp. Math. Appl."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/8\/131\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:44:17Z","timestamp":1760208257000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/9\/8\/131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,27]]},"references-count":60,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2017,8]]}},"alternative-id":["sym9080131"],"URL":"https:\/\/doi.org\/10.3390\/sym9080131","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2017,7,27]]}}}