Computing the hyperbolicity constant of a cubic graph

References

• J. Alonso, T. Brady, D. Cooper, T. Delzant, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro, and H. Short. notes on word hyperbolic groups, in Group Theory from a Geometrical Viewpoint, E. Ghys, A.A. Haefliger and A. Verjovsky, eds., World Scientific, Singapore, 1992, pp. 3–64.
   Google Scholar
• S. Bermudo, J.M. Rodríguez, and J.M. Sigarreta, Small values of the hyperbolicity constant in graphs. Submitted.
   Google Scholar
• S. Bermudo, J.M. Rodríguez, and J.M. Sigarreta, Computing the hyperbolicity constant, Comput. Math. Appl. 62 (2011), pp. 4592–4595. doi: 10.1016/j.camwa.2011.10.041
   Web of Science ®Google Scholar
• S. Bermudo, J.M. Rodríguez, J.M. Sigarreta, and E. Tourís, Hyperbolicity and complement of graphs, Appl. Math. Lett. 24 (2011), pp. 1882–1887. doi: 10.1016/j.aml.2011.05.011
   Web of Science ®Google Scholar
• S. Bermudo, J.M. Rodríguez, J.M. Sigarreta, and J.-M. Vilaire, Gromov hyperbolic graphs, Discret. Math. 313 (2013), pp. 1575–1585. doi: 10.1016/j.disc.2013.04.009
   Web of Science ®Google Scholar
• B.H. Bowditch, Notes on Gromov's hyperbolicity criterion for path-metric spaces, in Group Theory from a Geometrical Viewpoint, Trieste, 1990, E. Ghys, A. Haefliger and A. Verjovsky, eds., World Scientific, River Edge, NJ, 1991, 64–167.
   Google Scholar
• P.L. Bowers, Negatively curved graph and planar metrics with applications to type, Michigan Math. J. 45 (1998), pp. 31–53. doi: 10.1307/mmj/1030132082
   Google Scholar
• G. Brinkmann, J. Koolen, and V. Moulton, On the hyperbolicity of chordal graphs, Ann. Comb. 5 (2001), pp. 61–69. doi: 10.1007/s00026-001-8007-7
   Google Scholar
• P. Buser, Cubic graphs and the first eigenvalue of a Riemann surface, Math. Z. 162 (1978), pp. 87–99. doi: 10.1007/BF01437826
   Web of Science ®Google Scholar
• W. Carballosa, J.M. Rodríguez, J.M. Sigarreta, and M. Villeta, Gromov hyperbolicity of line graphs, Electr. J. Comb. 18 (2011), pp. 1–18.
   Google Scholar
• W. Carballosa, D. Pestana, J.M. Rodríguez, and J.M. Sigarreta, Distortion of the hyperbolicity constant of a graph, Electr. J. Comb. 19 (2012), pp. 1–18. doi: 10.1016/j.elecom.2012.03.006
   Web of Science ®Google Scholar
• W. Carballosa, R.M. Casablanca, A. de la Cruz, and J.M. Rodríguez, Gromov hyperbolicity in strong product graphs, Electr. J. Comb. 20(3) (2013), pp. P2.
   Google Scholar
• R. Charney, Artin groups of finite type are biautomatic, Math. Ann. 292 (1992), pp. 671–683. doi: 10.1007/BF01444642
   Web of Science ®Google Scholar
• I. Chavel, Eigenvalues in Riemannian Geometry, Academic Press, New York, 1984.
   Google Scholar
• B. Chen, S-T. Yau, and Y-N. Yeh, Graph homotopy and Graham homotopy, Discrete Math. 241 (2001), pp. 153–170. doi: 10.1016/S0012-365X(01)00115-7
   Web of Science ®Google Scholar
• V. Chepoi and B. Estellon, Packing and covering δ-hyperbolic spaces by balls, APPROX-RANDOM 2007, pp. 59–73.
   Google Scholar
• V. Chepoi, F.F. Dragan, B. Estellon, M. Habib, and Y. Vaxes, Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs, Electr. Notes Discre. Math. 31 (2008), pp. 231–234. doi: 10.1016/j.endm.2008.06.046
   Google Scholar
• M. DeVos and B. Mohar, An analogue of the Descartes-Euler formula for infinite graph and Higuchi's conjecture, Trans. Amer. Math. Soc. 359 (2007), pp. 3275–3286. doi: 10.1090/S0002-9947-07-04125-6
   Web of Science ®Google Scholar
• R. Diestel, Graph Theory, Heidelberg Graduate Texts in Mathematics, Vol. 173, Springer-Verlag, Berlin, 2010.
   Google Scholar
• D. Eppstein, Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition (SODA’2007), Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, New Orleans, pp. 29–38.
   Google Scholar
• R. Frigerio and A. Sisto, Characterizing hyperbolic spaces and real trees, Geom. Dedicata 142 (2009), pp. 139–149. doi: 10.1007/s10711-009-9363-4
   Web of Science ®Google Scholar
• C. Gavoille and O. Ly, Distance labeling in hyperbolic graphs, ISAAC 2005, Catania (italia), pp. 171–179.
   Google Scholar
• E. Ghys and P. de la Harpe, Sur les Groupes Hyperboliques d'après Mikhael Gromov, Progress in Mathematics, Vol. 83, Birkhäuser Boston Inc., Boston, MA, 1990.
   Google Scholar
• M. Gromov, Hyperbolic groups, in Essays in Group Theory, S.M. Gersten, ed., M. S. R. I. Publ. Vol. 8. Springer, Berlin, 1987, pp. 75–263.
   Google Scholar
• M. Gromov (with appendices by M. Katz, P. Pansu and S. Semmes), Metric Structures for Riemannian and Non-Riemannnian Spaces, Progress in Mathematics, Vol. 152, Birkhäuser, Berlin, 1999.
   Google Scholar
• E. Jonckheere and P. Lohsoonthorn, A Hyperbolic Geometry Approach to Multipath Routing, Proceedings of the 10th Mediterranean Conference on Control and Automation (MED 2002), Lisbon, Portugal, July 2002. FA5-1.
   Google Scholar
• E.A. Jonckheere, Contrôle du traffic sur les réseaux à géométrie hyperbolique–Vers une théorie géométrique de la sécurité l'acheminement de l'information, J. Eur. Syst. Autom. 8 (2002), pp. 45–60.
   Google Scholar
• E.A. Jonckheere and P. Lohsoonthorn, Geometry of network security, Amer. Control Conf. ACC, 2004, pp. 111–151.
   Google Scholar
• E.A. Jonckheere, P. Lohsoonthorn, and F. Ariaesi, Upper bound on scaled Gromov-hyperbolic delta, Appl. Math. Comp. 192 (2007), pp. 191–204. doi: 10.1016/j.amc.2007.03.001
   Web of Science ®Google Scholar
• E.A. Jonckheere, P. Lohsoonthorn, and F. Bonahon, Scaled Gromov hyperbolic graphs, J. Graph Theory 2 (2007), pp. 157–180.
   Google Scholar
• J.H. Koolen and V. Moulton, Hyperbolic bridged graphs, Eur. J. Comb. 23 (2002), pp. 683–699. doi: 10.1006/eujc.2002.0591
   Web of Science ®Google Scholar
• R. Krauthgamer and J.R. Lee, Algorithms on Negatively Curved Spaces, FOCS, 2006.
   Google Scholar
• D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá, Hyperbolic geometry of complex networks, Phys. Rev. E 82 (2010), article no. 036106, pp. 1–18. doi: 10.1103/PhysRevE.82.036106
   Web of Science ®Google Scholar
• J. Michel, J.M. Rodríguez, J.M. Sigarreta, and M. Villeta, Gromov hyperbolicity in cartesian product graphs, Proc. Indian Acad. Sci. Math. Sci. 120 (2010), pp. 1–17.
   Google Scholar
• J. Michel, J.M. Rodríguez, J.M. Sigarreta, and M. Villeta, Hyperbolicity and parameters of graphs, Ars Comb. 100 (2011), pp. 430–63.
   Google Scholar
• O. Narayan and I. Saniee, Large-scale curvature of networks, Phys. Rev. E 84 (2011), article no. 066108, pp. 1–8. doi: 10.1103/PhysRevE.84.066108
   Web of Science ®Google Scholar
• K. Oshika, Discrete Groups, AMS Bookstore, New York, 2002.
   Google Scholar
• D. Pestana, J.M. Rodríguez, J.M. Sigarreta, and M. Villeta, Gromov hyperbolic cubic graphs, Central Eur. J. Math. 10(3) (2012), pp. 1141–1151. doi: 10.2478/s11533-012-0036-4
   Web of Science ®Google Scholar
• A. Portilla, J.M. Rodríguez, J.M. Sigarreta, and E. Tourís, Gromov hyperbolic directed graphs, Acta Math. Appl. Sin. to appear.
   Web of Science ®Google Scholar
• A. Portilla, J.M. Rodríguez,, J.M. Sigarreta, and J-M. Vilaire, Gromov hyperbolic tessellation graphs, Utilitas Math. to appear, Preprint. Available at http://gama.uc3m.es/index.php/jomaro.html
   Google Scholar
• A. Portilla, J.M. Rodríguez, and E. Tourís, Gromov hyperbolicity through decomposition of metric spaces II, J. Geom. Anal. 14 (2004), pp. 123–149. doi: 10.1007/BF02921869
   Web of Science ®Google Scholar
• A. Portilla and E. Tourís, A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat. 53 (2009), pp. 83–110. doi: 10.5565/PUBLMAT_53109_04
   Web of Science ®Google Scholar
• J.M. Rodríguez and E. Tourís, Gromov hyperbolicity through decomposition of metric spaces, Acta Math. Hung. 103 (2004), pp. 53–84. doi: 10.1023/B:AMHU.0000028240.16521.9d
   Web of Science ®Google Scholar
• J.M. Rodríguez, J.M. Sigarreta, J-M. Vilaire, and M. Villeta, On the hyperbolicity constant in graphs, Discre. Math. 311 (2011), pp. 211–219. doi: 10.1016/j.disc.2010.11.005
   Web of Science ®Google Scholar
• J.M. Rodríguez and Sigarreta, Bounds on Gromov hyperbolicity constant in graphs, Proc. Indian Acad. Sci. Math. Sci. 122 (2012), pp. 53–65. doi: 10.1007/s12044-012-0060-0
   Google Scholar
• Y. Shang, Lack of Gromov-hyperbolicity in small-world networks, Cent. Eur. J. Math. 10 (2012), pp. 1152–1158. doi: 10.2478/s11533-012-0032-8
   Web of Science ®Google Scholar
• Y. Shang, Non-hyperbolicity of random graphs with given expected degrees, Stoch. Models 29 (2013), pp. 451–462. doi: 10.1080/15326349.2013.838510
   Web of Science ®Google Scholar
• Y. Shavitt and T. Tankel, On Internet Embedding in Hyperbolic Spaces for Overlay Construction and Distance Estimation, INFOCOM 2004.
   Google Scholar
• J.M. Sigarreta, Hyperbolicity in median graphs, Proc. Indian Acad. Sci. Math. Sci. 123(4) (2013), pp. 455–467. doi: 10.1007/s12044-013-0149-0
   Google Scholar
• E. Tourís, Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl. 380 (2011), pp. 865–881. doi: 10.1016/j.jmaa.2011.02.067
   Web of Science ®Google Scholar
• H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), pp. 339–362. doi: 10.1090/S0002-9947-1932-1501641-2
   Google Scholar
• Y. Wu and C. Zhang, Chordality and hyperbolicity of a graph, Electr. J. Comb. 18 (2011), pp. P43. Available at http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p43/0
   Google Scholar