Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant. (English) Zbl 1414.05157
Summary: To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let \(\mathcal{G}(g, c, n)\) be the set of graphs \(G\) with girth \(g(G) = g\), circumference \(c(G) = c\), and \(n\) vertices; and let \(\mathcal{H}(g, c, m)\) be the set of graphs with girth \(g\), circumference \(c\), and \(m\) edges. In this work, we study the four following extremal problems on graphs: \(A(g, c, n) = \min \{\delta(G) \mid G \in \mathcal{G}(g, c, n) \}\), \(B(g, c, n) = \max \{\delta(G) \mid G \in \mathcal{G}(g, c, n) \}\), \(\alpha(g, c, m) = \min \{\delta(G) \mid \in \mathcal{H}(g, c, m) \}\) and \(\beta(g, c, m) = \max \{\delta(G) \mid G \in \mathcal{H}(g, c, m) \}\). In particular, we obtain bounds for \(A(g, c, n)\) and \(\alpha(g, c, m)\), and we compute the precise value of \(B(g, c, n)\) and \(\beta(g, c, m)\) for all values of \(g\), \(c\), \(n\) and \(m\).
MSC:
| 05C35 | Extremal problems in graph theory |
Keywords:
extremal problems on graphs; Gromov hyperbolicity; hyperbolicity constant; girth; circumference; geodesicReferences:
| [1] | Alonso, J.; Brady, T.; Cooper, D.; Delzant, T.; Ferlini, V.; Lustig, M.; Mihalik, M.; Shapiro, M.; Short, H., Notes on word hyperbolic groups, (Ghys, E.; Haefliger, A.; Verjovsky, A., Group Theory from a Geometrical Viewpoint (1992), World Scientific: World Scientific Singapore) · Zbl 0849.20023 |
| [2] | Balogh, Z. M.; Bonk, M., Gromov hyperbolicity and the Kobayashi metric on strictly pseudoconvex domains, Comment. Math. Helv., 75, 504-533 (2000) · Zbl 0986.32012 |
| [3] | Balogh, Z. M.; Buckley, S. M., Geometric characterizations of Gromov hyperbolicity, Invent. Math., 153, 261-301 (2003) · Zbl 1059.30038 |
| [4] | Bandelt, H.-J.; Chepoi, V., \(1\)-Hyperbolic Graphs, SIAM J. Discrete Math., 16, 323-334 (2003) · Zbl 1029.05043 |
| [5] | Bermudo, S.; Carballosa, W.; Rodríguez, J. M.; Sigarreta, J. M., On the hyperbolicity of edge-chordal and path-chordal graphs, Filomat, 30:9, 2599-2607 (2016) · Zbl 1462.05260 |
| [6] | Bermudo, S.; Rodríguez, J. M.; Rosario, O.; Sigarreta, J. M., Small values of the hyperbolicity constant in graphs, Discrete Math., 339, 3073-3084 (2016) · Zbl 1343.05112 |
| [7] | Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M., Computing the hyperbolicity constant, Comput. Math. Appl., 62, 4592-4595 (2011) · Zbl 1247.53043 |
| [8] | Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M.; Vilaire, J.-M., Gromov hyperbolic graphs, Discrete Math., 313, 1575-1585 (2013) · Zbl 1279.05017 |
| [9] | Bonk, M.; Heinonen, J.; Koskela, P., Uniformizing Gromov hyperbolic spaces, Astérisque, 270 (2001) · Zbl 0970.30010 |
| [10] | Bonk, M.; Schramm, O., Embeddings of Gromov hyperbolic spaces, Geom. Funct. Anal., 10, 266-306 (2000) · Zbl 0972.53021 |
| [11] | Brinkmann, G.; Koolen, J.; Moulton, V., On the hyperbolicity of chordal graphs, Ann. Comb., 5, 61-69 (2001) · Zbl 0985.05021 |
| [12] | Calegari, D.; Fujiwara, K., Counting subgraphs in hyperbolic graphs with symmetry, J. Math. Soc. Japan, 67, 1213-1226 (2015) · Zbl 1323.05064 |
| [13] | Carballosa, W.; Rodríguez, J. M.; Sigarreta, J. M., Hyperbolicity in the corona and join of graphs, Aequationes Math., 89, 1311-1327 (2015) · Zbl 1321.05170 |
| [14] | Carballosa, W.; Rodríguez, J. M.; Sigarreta, J. M.; Villeta, M., on the Hyperbolicity Constant of Line Graphs, Electron. J. Combin., 18, p210 (2011) · Zbl 1283.05236 |
| [15] | Chalopin, J.; Chepoi, V.; Papasoglu, P.; Pecatte, T., Cop and robber game and hyperbolicity, SIAM J. Discrete Math., 28:4, 1987-2007 (2015) · Zbl 1309.05126 |
| [16] | Chang, H.-C.; Lu, H.-I., Computing the Girth of a Planar Graph in Linear Time, SIAM J. Comput., 42, 3, 1077-1094 (2013) · Zbl 1272.05089 |
| [17] | Chen, W.; Fang, W.; Hu, G.; Mahoney, M. W., On the hyperbolicity of small-world and treelike random graphs, Internet Math., 9, 4, 434-491 (2013) · Zbl 1338.05244 |
| [18] | Chen, B.; Yau, S.-T.; Yeh, Y.-N., Graph homotopy and Graham homotopy, Discrete Math., 241, 153-170 (2001) · Zbl 0990.05120 |
| [19] | Chepoi, V.; Dragan, F. F.; Estellon, B.; Habib, M.; Vaxes, Y., Notes on diameters, centers, and approximating trees of \(\delta \)-hyperbolic geodesic spaces and graphs, Electr. Notes Discr. Math., 31, 231-234 (2008) · Zbl 1267.05077 |
| [20] | Cohen, N.; Coudert, D.; Lancin, A., (Nisse, Yann; et Rousseau, Nicolas; et Busnel, Franck, Algorithme Exact Et ApprochÉ Pour Le Calcul de L’HyperbolicitÉ D’Un Graphe (2013), Pornic: Pornic France), 1-4 |
| [21] | Coornaert, M.; Delzant, T.; Papadopoulos, A., (GÉometrie Et ThÉorie Des Groupes. GÉometrie Et ThÉorie Des Groupes, Lecture Notes in Mathematics, vol. 1441 (1990), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0727.20018 |
| [22] | Coudert, D.; Ducoffe, G., Recognition of \(C_4\)-Free and \(1 / 2\)-Hyperbolic Graphs, SIAM J. Discrete Math., 28, 1601-1617 (2014) · Zbl 1306.05233 |
| [23] | Coudert, D.; Ducoffe, G., On the hyperbolicity of bipartite graphs and intersection graphs, Discrete App. Math., 214, 187-195 (2016) · Zbl 1346.05243 |
| [24] | Fournier, H.; Ismail, A.; Vigneron, A., Computing the Gromov hyperbolicity of a discrete metric space, J. Inform. Proc. Lett., 115, 576-579 (2015) · Zbl 1328.68301 |
| [25] | Frigerio, R.; Sisto, A., Characterizing hyperbolic spaces and real trees, Geom. Dedicata, 142, 139-149 (2009) · Zbl 1180.53045 |
| [26] | Ghys, E.; de la Harpe, P., Sur les Groupes Hyperboliques d’après Mikhael Gromov, (Progress in Mathematics, Vol. 83 (1990), Birkhäuser Boston Inc: Birkhäuser Boston Inc Boston, MA) · Zbl 0731.20025 |
| [27] | Gromov, M., Hyperbolic groups, in “Essays in group theory, (Gersten, S. M., Math. Sci. Res. Inst. Publ. Vol. 8 (1987), Springer), 75-265 |
| [28] | Hernández, V.; Pestana, D.; Rodríguez, J. M., Bounds on Gromov Hyperbolicity Constant, RACSAM, 110:2, 321-342 (2016) · Zbl 1348.05168 |
| [29] | Hernández, V.; Pestana, D.; Rodríguez, J. M., On a classical theorem on the diameter and minimum degree of a graph, Acta Math. Sinica, 33:11, 1477-1503 (2017) · Zbl 1386.05162 |
| [30] | Jonckheere, E. A., Controle du trafic sur les reseaux a geometrie hyperbolique-Une approche mathematique a la securite de l’acheminement de l’information, J. Europ. Syst. Autom., 37, 145-159 (2003) |
| [31] | Jonckheere, E. A.; Lohsoonthorn, P., Geometry of network security, (American Control Conference ACC (2004)), 111-151 |
| [32] | W.S. Kennedy, O. Narayan, I. Saniee, On the Hyperbolicity of Large-Scale Networks, CoRR, abs/1307.0031:1-22, 2013.; W.S. Kennedy, O. Narayan, I. Saniee, On the Hyperbolicity of Large-Scale Networks, CoRR, abs/1307.0031:1-22, 2013. |
| [33] | Koolen, J. H.; Moulton, V., Hyperbolic Bridged Graphs, European J. Combin., 23, 683-699 (2002) · Zbl 1027.05035 |
| [34] | Krioukov, D.; Papadopoulos, F.; Kitsak, M.; Vahdat, A.; Boguñá, M., Hyperbolic geometry of complex networks, Phys. Rev. E, 82, 036106 (2010) |
| [35] | Lang, U., Extendability of large-scale Lipschitz maps, Trans. Amer. Math. Soc., 351, 3975-3988 (1999) · Zbl 1010.54016 |
| [36] | Li, S.; Tucci, G. H., Traffic Congestion in Expanders, \((p, \delta)\)-Hyperbolic Spaces and Product of Trees, Internet Math., 11:2, 134-142 (2015) · Zbl 1475.53046 |
| [37] | Martínez-Pérez, A., Chordality properties and hyperbolicity on graphs, Electron. J. Combin., 23, 3, P3.51 (2016) · Zbl 1351.05158 |
| [38] | Michel, J.; Rodríguez, J. M.; Sigarreta, J. M.; Villeta, M., Hyperbolicity and parameters of graphs, Ars Combin., 100, 43-63 (2011) · Zbl 1265.05200 |
| [39] | F. Montgolfier, M. Soto, L. Viennot, Treewidth and Hyperbolicity of the Internet, In: 10th IEEE International Symposium on Network Computing and Applications (NCA), 2011, pp. 25-32.; F. Montgolfier, M. Soto, L. Viennot, Treewidth and Hyperbolicity of the Internet, In: 10th IEEE International Symposium on Network Computing and Applications (NCA), 2011, pp. 25-32. |
| [40] | Papasoglu, P., An algorithm detecting hyperbolicity, (Geometric and Computational Perspectives on Infinite Groups. Geometric and Computational Perspectives on Infinite Groups, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 25 (1996), AMS), 193-200 · Zbl 0857.20017 |
| [41] | Pestana, D.; Rodríguez, J. M.; Sigarreta, J. M.; Villeta, M., Gromov hyperbolic cubic graphs, Central Europ. J. Math., 10, 3, 1141-1151 (2012) · Zbl 1239.05141 |
| [42] | Portilla, A.; Rodríguez, J. M.; Sigarreta, J. M.; Vilaire, J.-M., Gromov hyperbolic tessellation graphs, Util. Math., 97, 193-212 (2015) · Zbl 1339.05324 |
| [43] | Portilla, A.; Rodríguez, J. M.; Tourís, E., Gromov hyperbolicity through decomposition of metric spaces II, J. Geom. Anal., 14, 123-149 (2004) · Zbl 1047.30028 |
| [44] | Portilla, A.; Tourís, E., A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat., 53, 83-110 (2009) · Zbl 1153.53320 |
| [45] | Rodríguez, J. M.; Sigarreta, J. M.; Vilaire, J.-M.; Villeta, M., On the hyperbolicity constant in graphs, Discrete Math., 311, 211-219 (2011) · Zbl 1226.05147 |
| [46] | Shang, Y., Lack of Gromov-hyperbolicity in colored random networks, Pan-American Math. J., 21, 1, 27-36 (2011) · Zbl 1230.05264 |
| [47] | Shang, Y., Lack of Gromov-hyperbolicity in small-world networks, Cent. Eur. J. Math., 10, 3, 1152-1158 (2012) · Zbl 1242.05257 |
| [48] | Shang, Y., Non-hyperbolicity of random graphs with given expected degrees, Stoch. Models, 29, 4, 451-462 (2013) · Zbl 1280.05125 |
| [49] | Shang, Y., On the likelihood of forests, Phys A: Stat. Mech. Appl., 456, 157-166 (2016) · Zbl 1400.05214 |
| [50] | Shavitt, Y.; Tankel, T., On internet embedding in hyperbolic spaces for overlay construction and distance estimation, IEEE/ACM Trans. Netw., 16:1, 25-36 (2008) |
| [51] | Sigarreta, J. M., Hyperbolicity in median graphs, Proc. Indian Acad. Sci. Math. Sci., 123, 455-467 (2013) · Zbl 1307.05164 |
| [52] | Tourís, E., Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl., 380, 865-881 (2011) · Zbl 1219.53047 |
| [53] | Väisälä, J., Gromov hyperbolic spaces, Expo. Math., 23, 187-231 (2005) · Zbl 1087.53039 |
| [54] | Verbeek, K.; Suri, S., Metric embeddings, hyperbolic space and social networks, Comput. Geom., 59, 1-12 (2016) · Zbl 1350.05106 |
| [55] | C. Wang, E. Jonckheere, T. Brun, Ollivier-Ricci curvature and fast approximation to tree-width in embeddability of QUBO problems, Proceedings of 6th International Symposium on Communications, Control, and Signal Processing (ISCCSP 2014).; C. Wang, E. Jonckheere, T. Brun, Ollivier-Ricci curvature and fast approximation to tree-width in embeddability of QUBO problems, Proceedings of 6th International Symposium on Communications, Control, and Signal Processing (ISCCSP 2014). |
| [56] | Weimann, O.; Yuster, R., Computing the girth of a planar graph in \(O(n \log n)\) time, Siam J. Discr. Math., 24:2, 609-616 (2010) · Zbl 1213.05152 |
| [57] | Wu, Y.; Zhang, C., Chordality and Hyperbolicity of a Graph, Electr. J. Comb., 18, P43 (2011) · Zbl 1220.05020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
