×

Non-hyperbolicity in random regular graphs and their traffic characteristics. (English) Zbl 1277.05153

Summary: In this paper we prove that random \(d\)-regular graphs with \(d \geq 3\) have traffic congestion of the order \(O(n \log^3_{d-1} n)\) where \(n\) is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically \(\delta \)-hyperbolic for any non-negative \(\delta \) almost surely as \(n \rightarrow \infty \).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C75 Structural characterization of families of graphs
05C82 Small world graphs, complex networks (graph-theoretic aspects)
20F67 Hyperbolic groups and nonpositively curved groups
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baryshnikov Yu., Tucci G.H., Asymptotic traffic flow in a hyperbolic network: definition and properties of the core, preprint available at http://arxiv.org/abs/1010.3304;
[2] Baryshnikov Yu., Tucci G.H., Asymptotic traffic flow in a hyperbolic network: non-uniform traffic, preprint available at http://arxiv.org/abs/1010.3305;
[3] Benjamini I., Expanders are not hyperbolic, Israel J. Math., 1998, 108, 33-36 http://dx.doi.org/10.1007/BF02783040; · Zbl 0915.05072
[4] Benjamini I., Hoppen C., Ofek E., Prałat P., Wormald N., Geodesics and almost geodesic cycles in random regular graphs, J. Graph Theory, 2011, 66(2), 115-136 http://dx.doi.org/10.1002/jgt.20496; · Zbl 1218.05074
[5] Bollobás B., Fernandez de la Vega W., The diameter of random regular graphs, Combinatorica, 1982, 2(2), 125-134 http://dx.doi.org/10.1007/BF02579310; · Zbl 0505.05053
[6] Brisdon M.R., Haefliger A., Metric Spaces of Non-Positive Curvature, Grundlehren Math. Wiss., 319, Springer, Berlin, 1999;
[7] 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; · Zbl 0634.20015
[8] Jonckheere E.A., Lohsoonthorn P., A hyperbolic geometry approach to multi-path routing, In: Proceedings of the 10th Mediterranean Conference on Control and Automation, Lisbon, July 9-12, 2002, available at http://med.ee.nd.edu/MED10/pdf/373.pdf;
[9] Jonckheere E., Lohsoonthorn P., Geometry of network security, In: Proceedings of the 2004 American Control Conference, 6, 2004, available at http://eudoxus2.usc.edu/CHAOS/paper4.pdf;
[10] Jonckheere E.A., Lou M., Hespanha J., Barooah P., Effective resistance of Gromov-hyperbolic graphs: application to asymptotic sensor network problems, In: Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, 2007, 1453-1458;
[11] Krioukov D., Papadopoulos F., Kitsak M., Vahdat A., Boguñá M., Hyperbolic geometry of complex networks, Phys. Rev. E, 2010, 82(3), #036106;
[12] Narayan O., Saniee I., Large-scale curvature of networks, Phys. Rev. E, 2011, 84, #066108;
[13] Shang Y., Lack of Gromov-hyperbolicity in small-world networks, Cent. Eur. J. Math., 2012, 10(3), 1152-1158 http://dx.doi.org/10.2478/s11533-012-0032-8; · Zbl 1242.05257
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.