Geodesics and Almost Geodesic Cycles in Random Regular Graphs

Autor(es)

Benjamini, Itai ^[1] ; Hoppen, Carlos ^[2] ; Ofek, Eran ^[3] ; Pratat, Pawet ^[4] ; Wormald, Nick ^[5]

Afiliação do(s) autor(es)

^[1] Weizmann Inst Sci, Dept Math, IL-76100 Rehovot - Israel

^[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil

^[3] Weizmann Inst Sci, Dept Comp Sci & Appl Math, IL-76100 Rehovot - Israel

^[4] W Virginia Univ, Dept Math, Morgantown, WV 26506 - USA

^[5] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1 - Canada

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF GRAPH THEORY; v. 66, n. 2, p. 115-136, FEB 2011.
• Citações Web of Science: 4

Resumo

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011 (AU)

• Processo FAPESP: 07/56496-3 - A análise de estruturas discretas de grandes proporções
• Beneficiário: Carlos Hoppen
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado