Gromov hyperbolic cubic graphs

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

Open Mathematics, Tome 10 (2012), p. 1141-1151 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2012-01-01

Zbl 1239.05141

EUDML-ID : urn:eudml:doc:269451

Bibliographie

[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 | Zbl 1115.53030

[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 | Zbl 1059.30038

[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 | Zbl 1247.53043

[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 | Zbl 1242.05061

[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] 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 | Zbl 1279.05017

[7] Bonk M., Heinonen J., Koskela P., Uniformizing Gromov hyperbolic spaces, Astérisque, 2001, #270

[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 | Zbl 0843.20031

[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 | Zbl 0977.53034

[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 | Zbl 0985.05021

[11] Carballosa W., Pestana D., Rodríguez J.M., Sigarreta J.M., Distortion of the hyperbolicity constant of a graph (submitted) | Zbl 1243.05182

[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 | Zbl 1283.05236

[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] 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 | Zbl 1117.05026

[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] 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 | Zbl 1200.05157

[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] 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 | Zbl 1180.53045

[19] Ghys E., de la Harpe P. (Eds.), Sur les Groupes Hyperboliques d’après Mikhael Gromov, Progr. Math., 83, Birkhäuser, Boston, 1990 | Zbl 0731.20025

[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] Gromov M. Metric Structures for Riemannian and Non-Riemannian Spaces, Progr. Math., 152, Birkhäuser, Boston, 1999

[22] Hästö P.A., Gromov hyperbolicity of the j G and $\tilde{j}_G $ metrics, Proc. Amer. Math. Soc., 2006, 134(4), 1137–1142 http://dx.doi.org/10.1090/S0002-9939-05-08053-6

[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 | Zbl 1262.30044

[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 | Zbl 1195.30061

[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 | Zbl 1190.30030

[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 | Zbl 1214.30035

[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) | Zbl 1289.30219

[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] 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] Jonckheere E., Lohsoonthorn P., Geometry of network security, In: American Control Conference, vol. 2, Boston, June 30–July 2, 2004, 976–981

[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 | Zbl 1193.53108

[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 | Zbl 1160.05017

[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] 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 | Zbl 1268.05172

[35] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Hyperbolicity and parameters of graphs, Ars Combin., 2011, 100, 43–63 | Zbl 1265.05200

[36] Ohshika K., Discrete Groups, Transl. Math. Monogr., 207, American Mathematical Society, Providence, 2002 | Zbl 1006.20031

[37] Portilla A., Rodríguez J.M., Sigarreta J.M., Tourís E., Gromov hyperbolic directed graphs (submitted)

[38] Portilla A., Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Gromov hyperbolic tessellation graphs, Util. Math. (in press) | Zbl 06592306

[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 | Zbl 1047.30028

[40] Portilla A., Rodríguez J.M., Tourís E., Stability of Gromov hyperbolicity, J. Adv. Math. Stud., 2009, 2(2), 77–96 | Zbl 1205.30039

[41] Portilla A., Tourís E., A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat., 2009, 53(1), 83–110 | Zbl 1153.53320

[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 | Zbl 1226.05147

[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 | Zbl 1051.30036

[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 | Zbl 1111.53033

[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 | Zbl 1115.30050

[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] 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 | Zbl 1219.53047

[48] Wu Y., Zhang C., Hyperbolicity and chordality of a graph, Electron. J. Combin., 2011, 18(1), #P43 | Zbl 1220.05020