Non-hyperbolicity in random regular graphs and their traffic characteristics

Gabriel Tucci

Open Mathematics (2013)

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

Abstract

top
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 → ∞.

How to cite

top

Gabriel 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. [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. [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. [3] Benjamini I., Expanders are not hyperbolic, Israel J. Math., 1998, 108, 33–36 http://dx.doi.org/10.1007/BF02783040 Zbl0915.05072
  4. [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. [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. [6] Brisdon M.R., Haefliger A., Metric Spaces of Non-Positive Curvature, Grundlehren Math. Wiss., 319, Springer, Berlin, 1999 
  7. [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. [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. [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. [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. [11] Krioukov D., Papadopoulos F., Kitsak M., Vahdat A., Boguñá M., Hyperbolic geometry of complex networks, Phys. Rev. E, 2010, 82(3), #036106 
  12. [12] Narayan O., Saniee I., Large-scale curvature of networks, Phys. Rev. E, 2011, 84, #066108 
  13. [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 ?

top

You must be logged in to post comments.