×

Mathematical properties of the hyperbolicity of circulant networks. (English) Zbl 1336.05123

Summary: If \(X\) is a geodesic metric space and \(x_1, x_2, x_3 \in 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 \(\delta\)-hyperbolic (in the Gromov sense) if any side of \(T\) is contained in a \(\delta\)-neighborhood of the union of the two other sides, for every geodesic triangle \(T\) in \(X\). The study of the hyperbolicity constant in networks is usually a very difficult task; therefore, it is interesting to find bounds for particular classes of graphs. A network is circulant if it has a cyclic group of automorphisms that includes an automorphism taking any vertex to any other vertex. In this paper we obtain several sharp inequalities for the hyperbolicity constant of circulant networks; in some cases we characterize the graphs for which the equality is attained.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
53C70 Direct methods (\(G\)-spaces of Busemann, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gromov, M.; Gersten, S. M., Hyperbolic groups, Essays in Group Theory. Essays in Group Theory, Mathematical Sciences Research Institute Publications, 8, 75-263 (1987), New York, NY, USA: Springer, New York, NY, USA · Zbl 0634.20015 · doi:10.1007/978-1-4613-9586-7_3
[2] Oshika, K., Discrete Groups (2002), AMS Bookstore · Zbl 1006.20031
[3] Charney, R., Artin groups of finite type are biautomatic, Mathematische Annalen, 292, 1, 671-683 (1992) · Zbl 0736.57001 · doi:10.1007/BF01444642
[4] Serrano, M. Á.; Boguñá, M.; Sagués, F., Uncovering the hidden geometry behind metabolic networks, Molecular BioSystems, 8, 3, 843-850 (2012) · doi:10.1039/c2mb05306c
[5] Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Physical Review E, 71, 5 (2005) · doi:10.1103/physreve.71.056103
[6] Shavitt, Y.; Tankel, T., On internet embedding in hyperbolic spaces for overlay construction and distance estimation, Proceedings of the IEEE Conference on Computer Communications (INFOCOM ’04)
[7] Krioukov, D.; Papadopoulos, F.; Kitsak, M.; Vahdat, A.; Boguñá, M., Hyperbolic geometry of complex networks, Physical Review E, 82, 3 (2010) · doi:10.1103/physreve.82.036106
[8] Chepoi, V.; Estellon, B., Packing and covering \(δ\)-hyperbolic spaces by balls, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM ’07)
[9] Jonckheere, E. A.; Lohsoonthorn, P., Geometry of network security, Proceedings of the American Control Conference (ACC ’04), IEEE
[10] Bermudo, S.; Carballosa, W.; Rodríguez, J. M.; Sigarreta, J. M., On the hyperbolicity of edge-chordal and path chordal graphs, Filomat · Zbl 1462.05260
[11] Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M., Computing the hyperbolicity constant, Computers and Mathematics with Applications, 62, 12, 4592-4595 (2011) · Zbl 1247.53043 · doi:10.1016/j.camwa.2011.10.041
[12] Bermudo, S.; Rodríguez, J. M.; Rosario, O.; Sigarreta, J. M., Graphs with small hyperbolicity constant, Electronic Notes in Discrete Mathematics, 46, 265-272 (2014) · Zbl 1338.05060 · doi:10.1016/j.endm.2014.08.035
[13] Bermudo, S.; Rodríguez, J. M.; Sigarreta, J. M.; Vilaire, J.-M., Gromov hyperbolic graphs, Discrete Mathematics, 313, 15, 1575-1585 (2013) · Zbl 1279.05017 · doi:10.1016/j.disc.2013.04.009
[14] Brinkmann, G.; Koolen, J. H.; Moulton, V., On the hyperbolicity of chordal graphs, Annals of Combinatorics, 5, 1, 61-69 (2001) · Zbl 0985.05021 · doi:10.1007/s00026-001-8007-7
[15] Carballosa, W.; Rodríguez, J. M.; Sigarreta, J. M., Hyperbolicity in the corona and join of graphs, Aequationes mathematicae, 89, 5, 1311-1327 (2015) · Zbl 1321.05170 · doi:10.1007/s00010-014-0324-0
[16] Chepoi, V.; Dragan, F. F.; Estellon, B.; Habib, M.; Vaxès, Y., Notes on diameters, centers, and approximating trees of \(δ\)-hyperbolic geodesic spaces and graphs, Electronic Notes in Discrete Mathematics, 31, 231-234 (2008) · Zbl 1267.05077 · doi:10.1016/j.endm.2008.06.046
[17] Michel, J.; Rodríguez, J. M.; Sigarreta, J. M.; Villeta, M., Hyperbolicity and parameters of graphs, Ars Combinatoria, 100, 43-63 (2011) · Zbl 1265.05200
[18] Rodríguez, J. M.; Sigarreta, J. M.; Vilaire, J.-M.; Villeta, M., On the hyperbolicity constant in graphs, Discrete Mathematics, 311, 4, 211-219 (2011) · Zbl 1226.05147 · doi:10.1016/j.disc.2010.11.005
[19] Tourís, E., Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, Journal of Mathematical Analysis and Applications, 380, 2, 865-881 (2011) · Zbl 1219.53047 · doi:10.1016/j.jmaa.2011.02.067
[20] Wu, Y.; Zhang, C., Chordality and hyperbolicity of a graph, The Electronic Journal of Combinatorics, 18, 1, article P43 (2011) · Zbl 1220.05020
[21] Ghys, E.; de la Harpe, P., Sur les Groupes Hyperboliques d’Après Mikhael Gromov. Sur les Groupes Hyperboliques d’Après Mikhael Gromov, Progress in Mathematics, 83 (1990), Boston, Mass, USA: Birkhäuser, Boston, Mass, USA · Zbl 0731.20025
[22] Alspach, B., Isomorphism and cayley graphs on abelian groups, Graph Symmetry (Montreal, {PQ}, 1996). Graph Symmetry (Montreal, {PQ}, 1996), Nato Science Series C: Mathematical and Physical Sciences, 497, 1-22 (1997), Dordrecht, The Netherlands: Kluwer Academic, Dordrecht, The Netherlands · Zbl 0884.05049
[23] Xu, J., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers · Zbl 1046.68026
[24] Wong, C. K.; Coppersmith, D., A combinatorial problem related to multimodule memory organization, Journal of the ACM, 21, 3, 392-402 (1974) · Zbl 0353.68039 · doi:10.1145/321832.321838
[25] Bermond, J. C.; Comellas, F.; Hsu, D. F., Distributed loop computer-networks: a survey, Journal of Parallel and Distributed Computing, 24, 1, 2-10 (1995) · doi:10.1006/jpdc.1995.1002
[26] Boesch, F. T.; Wang, J.-F., Reliable circulant networks with minimum transmission delay, IEEE Transactions on Circuits and Systems, 32, 12, 1286-1291 (1985) · Zbl 0583.94018 · doi:10.1109/tcs.1985.1085667
[27] Karlin, M., New binary coding results by circulants, IEEE Transactions on Information Theory, 15, 1, 81-92 (1969) · Zbl 0167.18104 · doi:10.1109/tit.1969.1054261
[28] Meijer, P. T., Connectivities and diameters of circulant graphs [Ph.D. thesis] (1991), Department of Mathematics and Statistics, Simon Fraser University
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.