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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.