# Non-hyperbolicity in random regular graphs and their traffic characteristics

Open Mathematics (2013)

- Volume: 11, Issue: 9, page 1593-1597
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topGabriel Tucci. "Non-hyperbolicity in random regular graphs and their traffic characteristics." Open Mathematics 11.9 (2013): 1593-1597. <http://eudml.org/doc/269768>.

@article{GabrielTucci2013,

abstract = {In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.},

author = {Gabriel Tucci},

journal = {Open Mathematics},

keywords = {Random regular graph; Hyperbolic spaces; Traffic flow; random regular graph; hyperbolic spaces; traffic flow},

language = {eng},

number = {9},

pages = {1593-1597},

title = {Non-hyperbolicity in random regular graphs and their traffic characteristics},

url = {http://eudml.org/doc/269768},

volume = {11},

year = {2013},

}

TY - JOUR

AU - Gabriel Tucci

TI - Non-hyperbolicity in random regular graphs and their traffic characteristics

JO - Open Mathematics

PY - 2013

VL - 11

IS - 9

SP - 1593

EP - 1597

AB - In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.

LA - eng

KW - Random regular graph; Hyperbolic spaces; Traffic flow; random regular graph; hyperbolic spaces; traffic flow

UR - http://eudml.org/doc/269768

ER -

## References

top- [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 Zbl0915.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 Zbl1218.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 Zbl0505.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
- [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 Zbl1242.05257

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.