Gromov hyperbolic cubic graphs

Domingo Pestana; José Rodríguez; José Sigarreta; María Villeta

Open Mathematics (2012)

  • Volume: 10, Issue: 3, page 1141-1151
  • ISSN: 2391-5455

Abstract

top
If X is a geodesic metric space and x 1; x 2; x 3 ∈ X, a geodesic triangle T = {x 1; x 2; x 3} is the union of the three geodesics [x 1 x 2], [x 2 x 3] and [x 3 x 1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.

How to cite

top

Domingo Pestana, et al. "Gromov hyperbolic cubic graphs." Open Mathematics 10.3 (2012): 1141-1151. <http://eudml.org/doc/269451>.

@article{DomingoPestana2012,
abstract = {If X is a geodesic metric space and x 1; x 2; x 3 ∈ X, a geodesic triangle T = \{x 1; x 2; x 3\} is the union of the three geodesics [x 1 x 2], [x 2 x 3] and [x 3 x 1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf \{δ ≥ 0: X is δ-hyperbolic\}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min \{3n/16 + 1; n/4\}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.},
author = {Domingo Pestana, José Rodríguez, José Sigarreta, María Villeta},
journal = {Open Mathematics},
keywords = {Infinite graphs; Cubic graphs; Gromov hyperbolicity; infinite graphs; cubic graphs},
language = {eng},
number = {3},
pages = {1141-1151},
title = {Gromov hyperbolic cubic graphs},
url = {http://eudml.org/doc/269451},
volume = {10},
year = {2012},
}

TY - JOUR
AU - Domingo Pestana
AU - José Rodríguez
AU - José Sigarreta
AU - María Villeta
TI - Gromov hyperbolic cubic graphs
JO - Open Mathematics
PY - 2012
VL - 10
IS - 3
SP - 1141
EP - 1151
AB - If X is a geodesic metric space and x 1; x 2; x 3 ∈ X, a geodesic triangle T = {x 1; x 2; x 3} is the union of the three geodesics [x 1 x 2], [x 2 x 3] and [x 3 x 1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.
LA - eng
KW - Infinite graphs; Cubic graphs; Gromov hyperbolicity; infinite graphs; cubic graphs
UR - http://eudml.org/doc/269451
ER -

References

top
  1. [1] Alvarez V., Portilla A., Rodriguez J.M., Touris E., Gromov hyperbolicity of Denjoy domains, Geom. Dedicata, 2006, 121, 221–245 http://dx.doi.org/10.1007/s10711-006-9102-z Zbl1115.53030
  2. [2] Balogh Z.M., Buckley S.M., Geometric characterizations of Gromov hyperbolicity, Invent. Math., 2003, 153(2), 261–301 http://dx.doi.org/10.1007/s00222-003-0287-6 Zbl1059.30038
  3. [3] Bermudo S., Rodríguez J.M., Sigarreta J.M., Computing the hyperbolicity constant, Comput. Math. Appl., 2011, 62(12), 4592–4595 http://dx.doi.org/10.1016/j.camwa.2011.10.041 Zbl1247.53043
  4. [4] Bermudo S., Rodríguez J.M., Sigarreta J.M., Tourís E., Hyperbolicity and complement of graphs, Appl. Math. Letters, 2011, 24(11), 1882–1887 http://dx.doi.org/10.1016/j.aml.2011.05.011 Zbl1242.05061
  5. [5] Bermudo S., Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., In: 8th International Conference of Numerical Analysis and Applied Mathematics, Rhodes, September 19–25, 2010, AIP Conf. Proc., 1281, 575–578 
  6. [6] Bermudo S., Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Gromov hyperbolic graphs, preprint available at http://gama.uc3m.es/images/gama_papers/jomaro/2010_18_brsv Zbl1279.05017
  7. [7] Bonk M., Heinonen J., Koskela P., Uniformizing Gromov hyperbolic spaces, Astérisque, 2001, #270 
  8. [8] Bowditch B.H., Notes on Gromov’s hyperbolicity criterion for path-metric spaces, In: Group Theory from a Geometrical Viewpoint, Trieste, March 26–April 6, 1990, World Scientific, River Edge, 1991, 64–167 Zbl0843.20031
  9. [9] Bowers P.L., Negatively curved graph and planar metrics with applications to type, Michigan Math. J., 1998, 45(1), 31–53 http://dx.doi.org/10.1307/mmj/1030132082 Zbl0977.53034
  10. [10] Brinkmann G., Koolen J., Moulton V., On the hyperbolicity of chordal graphs, Ann. Comb., 2001, 5(1), 61–69 http://dx.doi.org/10.1007/s00026-001-8007-7 Zbl0985.05021
  11. [11] Carballosa W., Pestana D., Rodríguez J.M., Sigarreta J.M., Distortion of the hyperbolicity constant of a graph (submitted) Zbl1243.05182
  12. [12] Carballosa W., Rodríguez J.M., Sigarreta J.M., Villeta M., On the hyperbolicity constant of line graphs, Electron. J. Combin., 2011, 18(1), #P210 Zbl1283.05236
  13. [13] Chen B., Yau S.-T., Yeh Y.-N., Graph homotopy and Graham homotopy, Discrete Math., 2001, 241(1–3), 153–170 http://dx.doi.org/10.1016/S0012-365X(01)00115-7 
  14. [14] DeVos M., Mohar B., An analogue of the Descartes-Euler formula for infinite graphs and Higuchi’s conjecture, Trans. Amer. Math. Soc., 2007, 359(7), 3287–3300 http://dx.doi.org/10.1090/S0002-9947-07-04125-6 Zbl1117.05026
  15. [15] Diestel R., Graph Theory, Grad. Texts in Math., 173, Springer, Heidelberg, 2010 http://dx.doi.org/10.1007/978-3-642-14279-6 
  16. [16] Fernau H., Rodríguez J.A., Sigarreta J.M., Offensive r-alliances in graphs, Discrete Appl. Math., 2009, 157(1), 177–182 http://dx.doi.org/10.1016/j.dam.2008.06.001 Zbl1200.05157
  17. [17] Fiedler M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J., 1975, 25(100)(4), 619–633 
  18. [18] Frigerio R., Sisto A., Characterizing hyperbolic spaces and real trees, Geom. Dedicata, 2009, 142, 139–149 http://dx.doi.org/10.1007/s10711-009-9363-4 Zbl1180.53045
  19. [19] Ghys E., de la Harpe P. (Eds.), Sur les Groupes Hyperboliques d’après Mikhael Gromov, Progr. Math., 83, Birkhäuser, Boston, 1990 Zbl0731.20025
  20. [20] Gromov M., Hyperbolic groups, In: Essays in Group Theory, Math. Sci. Res. Inst. Publ., 8, Springer, New York, 1987, 75–263 http://dx.doi.org/10.1007/978-1-4613-9586-7_3 
  21. [21] Gromov M. Metric Structures for Riemannian and Non-Riemannian Spaces, Progr. Math., 152, Birkhäuser, Boston, 1999 
  22. [22] Hästö P.A., Gromov hyperbolicity of the j G and j ˜ G metrics, Proc. Amer. Math. Soc., 2006, 134(4), 1137–1142 http://dx.doi.org/10.1090/S0002-9939-05-08053-6 
  23. [23] Hästö P., Lindén H., Portilla A., Rodríguez J.M., Tourís E., Gromov hyperbolicity of Denjoy domains with hyperbolic and quasihyperbolic metrics, J. Math. Soc. Japan, 2012, 64(1), 247–261 http://dx.doi.org/10.2969/jmsj/06410247 Zbl1262.30044
  24. [24] Hästö P., Portilla A., Rodríguez J.M., Tourís E., Gromov hyperbolic equivalence of the hyperbolic and quasihyperbolic metrics in Denjoy domains, Bull. Lond. Math. Soc., 2010, 42(2), 282–294 http://dx.doi.org/10.1112/blms/bdp125 Zbl1195.30061
  25. [25] Hästö P., Portilla A., Rodríguez J.M., Tourís E., Comparative Gromov hyperbolicity results for the hyperbolic and quasihyperbolic metrics, Complex Var. Elliptic Equ., 2010, 55(1–3), 127–135 Zbl1190.30030
  26. [26] Hästö P., Portilla A., Rodríguez J.M., Tourís E., Uniformly separated sets and Gromov hyperbolicity of domains with the quasihyperbolic metric, Mediterr. J. Math., 2011, 8(1), 49–67 http://dx.doi.org/10.1007/s00009-010-0059-7 Zbl1214.30035
  27. [27] Hästö P., Portilla A., Rodríguez J.M., Tourís E., Gromov hyperbolicity of Denjoy domains through fundamental domains, Publ. Math. Debrecen (in press) Zbl1289.30219
  28. [28] Jonckheere E. A., Contrôle du traffic sur les réseaux à géométrie hyperbolique. Vers une théorie géométrique de la sécurité de l’acheminement de l’information, Journal Européen des Systèmes Automatisés, 2003, 37(2), 145–159 http://dx.doi.org/10.3166/jesa.37.145-159 
  29. [29] Jonckheere E.A., Lohsoonthorn P., A hyperbolic geometry approach to multipath routing, In: 10th Mediterranean Conference on Control and Automation, Lisbon, July 9–12, 2002, available at http://med.ee.nd.edu/MED10/pdf/373.pdf 
  30. [30] Jonckheere E., Lohsoonthorn P., Geometry of network security, In: American Control Conference, vol. 2, Boston, June 30–July 2, 2004, 976–981 
  31. [31] Jonckheere E.A., Lohsoonthorn P., Ariaei F., Upper bound on scaled Gromov-hyperbolic δ, Appl. Math. Comput., 2007, 192(1), 191–204 http://dx.doi.org/10.1016/j.amc.2007.03.001 Zbl1193.53108
  32. [32] Jonckheere E., Lohsoonthorn P., Bonahon F., Scaled Gromov hyperbolic graphs, J. Graph Theory, 2008, 57(2), 157–180 http://dx.doi.org/10.1002/jgt.20275 Zbl1160.05017
  33. [33] Koolen J.H., Moulton V., Hyperbolic bridged graphs, European J. Combin., 2002, 23(6), 683–699 http://dx.doi.org/10.1006/eujc.2002.0591 
  34. [34] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Gromov hyperbolicity in Cartesian product graphs, Proc. Indian Acad. Sci. Math. Sci., 2010, 120(5), 593–609 http://dx.doi.org/10.1007/s12044-010-0048-6 Zbl1268.05172
  35. [35] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Hyperbolicity and parameters of graphs, Ars Combin., 2011, 100, 43–63 Zbl1265.05200
  36. [36] Ohshika K., Discrete Groups, Transl. Math. Monogr., 207, American Mathematical Society, Providence, 2002 Zbl1006.20031
  37. [37] Portilla A., Rodríguez J.M., Sigarreta J.M., Tourís E., Gromov hyperbolic directed graphs (submitted) 
  38. [38] Portilla A., Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Gromov hyperbolic tessellation graphs, Util. Math. (in press) Zbl06592306
  39. [39] Portilla A., Rodríguez J.M., Tourís E., Gromov hyperbolicity through decomposition of metric spaces II, J. Geom. Anal., 2004, 14(1), 123–149 http://dx.doi.org/10.1007/BF02921869 Zbl1047.30028
  40. [40] Portilla A., Rodríguez J.M., Tourís E., Stability of Gromov hyperbolicity, J. Adv. Math. Stud., 2009, 2(2), 77–96 Zbl1205.30039
  41. [41] Portilla A., Tourís E., A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat., 2009, 53(1), 83–110 Zbl1153.53320
  42. [42] Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Villeta M., On the hyperbolicity constant in graphs, Discrete Math., 2011, 311(4), 211–219 http://dx.doi.org/10.1016/j.disc.2010.11.005 Zbl1226.05147
  43. [43] Rodríguez J.M., Tourís E., Gromov hyperbolicity through decomposition of metric spaces, Acta Math. Hung., 2004, 103(1–2), 107–138 http://dx.doi.org/10.1023/B:AMHU.0000028240.16521.9d Zbl1051.30036
  44. [44] Rodríguez J.M., Tourís E., A new characterization of Gromov hyperbolicity for negatively curved surfaces, Publ. Mat., 2006, 50(2), 249–278 Zbl1111.53033
  45. [45] Rodríguez J.M., Tourís E., Gromov hyperbolicity of Riemann surfaces, Acta Math. Sinica (Engl. Ser.), 2007, 23(2), 209–228 http://dx.doi.org/10.1007/s10114-005-0547-z Zbl1115.30050
  46. [46] Sigarreta J.M., Alianzas en Grafos, PhD thesis, Universidad Carlos III, Madrid, 2007, available at http://e-archivo.uc3m.es/bitstream/10016/2455/1/Tesis_Jose_M_Sigarreta.pdf 
  47. [47] Tourís E., Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl., 2011, 380(2), 865–881 http://dx.doi.org/10.1016/j.jmaa.2011.02.067 Zbl1219.53047
  48. [48] Wu Y., Zhang C., Hyperbolicity and chordality of a graph, Electron. J. Combin., 2011, 18(1), #P43 Zbl1220.05020

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.