# Gromov hyperbolic cubic graphs

Open Mathematics (2012)

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

top

## 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 ${\stackrel{˜}{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.