On the hyperbolicity constant of circular-arc graphs. (English) Zbl 1414.05095
Summary: Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C76 | Graph operations (line graphs, products, etc.) |
References:
| [1] | Aouchiche, M.; Hansen, P., A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math., 161, 466-546 (2013) · Zbl 1259.05083 |
| [2] | 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 |
| [3] | 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 |
| [4] | Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M., Computing the hyperbolicity constant, Comput. Math. Appl., 62, 4592-4595 (2011) · Zbl 1247.53043 |
| [5] | Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M.; Tourís, E., Hyperbolicity and complement of graphs, Appl. Math. Lett., 24, 1882-1887 (2011) · Zbl 1242.05061 |
| [6] | Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M.; Vilaire, J.-M., Gromov hyperbolic graphs, Discrete Math., 313, 1575-1585 (2013) · Zbl 1279.05017 |
| [7] | Boguñá, M.; Papadopoulos, F.; Krioukov, D., Sustaining the internet with hyperbolic mapping, Nature Commun., 1, 62, 18 (2010) |
| [8] | Brandstädt, A.; Chepoi, V.; Dragan, F., Distance approximating trees for chordal and dually chordal graphs, J. Algor., 30, 166-184 (1999) · Zbl 0914.68148 |
| [9] | Brinkmann, G.; Koolen, J.; Moulton, V., On the hyperbolicity of chordal graphs, Ann. Comb., 5, 61-69 (2001) · Zbl 0985.05021 |
| [10] | Calegari, D.; Fujiwara, K., Counting subgraphs in hyperbolic graphs with symmetry, J. Math. Soc. Japan, 67, 1213-1226 (2015) · Zbl 1323.05064 |
| [11] | Carballosa, W.; Rodríguez, J. M.; Sigarreta, J. M., New inequalities on the hyperbolity constant of line graphs, Ars Combin., 129, 367-386 (2016) · Zbl 1413.05283 |
| [12] | Chalopin, J.; Chepoi, V.; Papasoglu, P.; Pecatte, T., Cop and robber game and hyperbolicity, SIAM J. Discrete Math., 28, 4, 1987 (2007) · Zbl 1309.05126 |
| [13] | Charney, R., Artin groups of finite type are biautomatic, Math. Ann., 292, 671-683 (1992) · Zbl 0736.57001 |
| [14] | Chen, B.; Yau, S.-T.; Yeh, Y.-N., Graph homotopy and Graham homotopy, Discrete Math., 241, 153-170 (2001) · Zbl 0990.05120 |
| [15] | 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 |
| [16] | N. Cohen, D. Coudert, A. Lancin, Algorithme exact et approché pour le calcul de l’hyperbolicité d’un graphe, in: Yann Nisse, Nicolas et Rousseau, Franck et Busnel (Eds.), Pornic, France, May 2013, pp. 1-4.; N. Cohen, D. Coudert, A. Lancin, Algorithme exact et approché pour le calcul de l’hyperbolicité d’un graphe, in: Yann Nisse, Nicolas et Rousseau, Franck et Busnel (Eds.), Pornic, France, May 2013, pp. 1-4. |
| [17] | 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 |
| [18] | Coudert, D.; Ducoffe, G., Data center interconnection networks are not hyperbolic, Theoret. Comput. Sci., 639, 72-90 (2016) · Zbl 1344.68173 |
| [19] | Coudert, D.; Ducoffe, G., On the hyperbolicity of bipartite graphs and intersection graphs, Discrete App. Math., 214, 187-195 (2016) · Zbl 1346.05243 |
| [20] | Fournier, H.; Ismail, A.; Vigneron, A., Computing the Gromov hyperbolicity of a discrete metric space, J. Inform. Proc. Letters, 115, 576-579 (2015) · Zbl 1328.68301 |
| [21] | Frigerio, R.; Sisto, A., Characterizing hyperbolic spaces and real trees, Geom. Dedicata, 142, 139-149 (2009) · Zbl 1180.53045 |
| [22] | 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 |
| [23] | Gromov, M., Hyperbolic groups, (Gersten, S. M., Essays in Group Theory. Essays in Group Theory, M. S. R. I. Publ, vol. 8 (1987), Springer), 75-263 · Zbl 0634.20015 |
| [24] | Hernández, V.; Pestana, D.; Rodríguez, J. M., Bounds on Gromov hyperbolicity constant, RACSAM, 110, 2, 321-342 (2016) · Zbl 1348.05168 |
| [25] | 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 |
| [26] | Hernández, J. C.; Reyes, R.; Rodríguez, J. M.; Sigarreta, J. M., Mathematical properties on the hyperbolicity of interval graphs, Symmetry, 9, 11, 1-13 (2017), 255 · Zbl 1423.05052 |
| [27] | 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é l’acheminement de l’information, J. Europ. Syst. Autom., 8, 45-60 (2002) |
| [28] | Jürgen, E., Extremal interval graphs, J. Graph Theory, 17, 117-127 (1993) · Zbl 0783.05058 |
| [29] | Koolen, J. H.; Moulton, V., Hyperbolic bridged graphs, European J. Combin., 23, 683-699 (2002) · Zbl 1027.05035 |
| [30] | Krauthgamer, R.; Lee, J. R., Algorithms on negatively curved spaces, (FOCS (2006)) |
| [31] | Krioukov, D.; Papadopoulos, F.; Kitsak, M.; Vahdat, A.; Boguá, M., Hyperbolic geometry of complex networks, Phys. Rev. E, 82, 036106 (2010) |
| [32] | 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 |
| [33] | Martínez-Pérez, A., Chordality properties and hyperbolicity on graphs, Electron. J. Combin., 23, 3, P3.51 (2016) · Zbl 1351.05158 |
| [34] | McConnell, R. M., Linear-time recognition of circular-arc graphs, Algorithmica, 37, 93-147 (2003) · Zbl 1060.68088 |
| [35] | McKee, T. A.; McMorris, F. R., Topics in Intersection Graph Theory (1999), SIAM · Zbl 0945.05003 |
| [36] | 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 |
| [37] | Nordhaus, E. A.; Gaddum, J., On complementary graphs, Amer. Math. Monthly, 63, 175-177 (1956) · Zbl 0070.18503 |
| [38] | Oshika, K., Discrete Groups (2002), AMS Bookstore · Zbl 1006.20031 |
| [39] | Pal, M., Intersection graphs: An introduction, Ann. Pure Appl. Math., 4, 43-91 (2013) |
| [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-211 (2015) · Zbl 1339.05324 |
| [43] | 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 |
| [44] | Shang, Y., Lack of Gromov-hyperbolicity in colored random networks, Pan-American Math. J., 21, 1, 27-36 (2011) · Zbl 1230.05264 |
| [45] | Shang, Y., Lack of Gromov-hyperbolicity in small-world networks, Cent. Eur. J. Math., 10, 1152-1158 (2012) · Zbl 1242.05257 |
| [46] | Shang, Y., Non-hyperbolicity of random graphs with given expected degrees, Stoch. Models, 29, 451-462 (2013) · Zbl 1280.05125 |
| [47] | Shang, Y., On the likelihood of forests, Physica A, 456, 157-166 (2016) · Zbl 1400.05214 |
| [48] | 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) |
| [49] | Sigarreta, J. M., Hyperbolicity in median graphs, Proc. Indian Acad. Sci. Math. Sci., 123, 455-467 (2013) · Zbl 1307.05164 |
| [50] | Tourís, E., Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl., 380, 865-881 (2011) · Zbl 1219.53047 |
| [51] | Verbeek, K.; Suri, S., Metric embeddings, hyperbolic space and social networks, Comput. Geom., 59, 1-12 (2016) · Zbl 1350.05106 |
| [52] | Wu, Y.; Zhang, C., Chordality and hyperbolicity of a graph, Electron. J. Combin., 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.
