PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2013 | 11 | 9 | 1593-1597
Tytuł artykułu

Non-hyperbolicity in random regular graphs and their traffic characteristics

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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 → ∞.
Twórcy
Bibliografia
  • [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
  • [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
  • [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
  • [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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-013-0268-y
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.