Gromov hyperbolic cubic graphs

• Autorzy: Domingo Pestana , José Rodríguez , José Sigarreta , María Villeta
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Infinite graphs; Cubic graphs; Gromov hyperbolicity

Kategorie tematyczne

• 05A20: Combinatorial inequalities
• 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2012
• Tom: 10
• Numer: 3
• Strony: 1141-1151

Daty

wydano

2012-06-01

online

2012-03-24

Twórcy

autor

Domingo Pestana

• Universidad Carlos III de Madrid

autor

José Rodríguez

• Universidad Carlos III de Madrid

autor

José Sigarreta

• Universidad Autónoma de Guerrero

autor

María Villeta

• Escuela Universitaria de Estadística, Universidad Complutense de Madrid

Bibliografia

• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [11] Carballosa W., Pestana D., Rodríguez J.M., Sigarreta J.M., Distortion of the hyperbolicity constant of a graph (submitted)
• [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
• [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
• [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
• [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
• [19] Ghys E., de la Harpe P. (Eds.), Sur les Groupes Hyperboliques d’après Mikhael Gromov, Progr. Math., 83, Birkhäuser, Boston, 1990
• [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
• [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
• [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
• [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
• [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)
• [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
• [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
• [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
• [35] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Hyperbolicity and parameters of graphs, Ars Combin., 2011, 100, 43–63
• [36] Ohshika K., Discrete Groups, Transl. Math. Monogr., 207, American Mathematical Society, Providence, 2002
• [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)
• [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
• [40] Portilla A., Rodríguez J.M., Tourís E., Stability of Gromov hyperbolicity, J. Adv. Math. Stud., 2009, 2(2), 77–96
• [41] Portilla A., Tourís E., A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat., 2009, 53(1), 83–110
• [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
• [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
• [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
• [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
• [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
• [48] Wu Y., Zhang C., Hyperbolicity and chordality of a graph, Electron. J. Combin., 2011, 18(1), #P43

Identyfikatory

DOI

10.2478/s11533-012-0036-4