Geodesics and almost geodesic cycles in random regular graphs
Geodesics and almost geodesic cycles in random regular graphs
复制标题
DOI：
10.1002/jgt.20496
复制
发表时间：
2006-10
影响因子：
0.9
通讯作者：
I. Benjamini;C. Hoppen;E. Ofek;P. Prałat;N. Wormald
中科院分区：
文献类型：
--
作者：
I. Benjamini;C. Hoppen;E. Ofek;P. Prałat;N. Wormald
图 G 中的测地线是 G 的两个顶点之间的最短路径。对于 n 的特定函数 e(n)，我们将 G 中的近测地线循环 C 定义为这样的循环，其中对于 C 中的每两个顶点 u 和 v，距离 dG(u, v) 至少为 dC(u, v)−e(n)。令 ω(n) 为任意 n 趋于无穷大的函数。我们考虑一个有 n 个顶点的随机 d-正则图。我们证明几乎所有的顶点对都属于几乎测地线循环 C，其中 e(n) = logd−1logd−1n+ ω(n) 和 |C| = 2logd−1n+ O(ω(n))。一路上，我们获得了近测地线路径的结果。我们还给出了该随机图中两个随机顶点之间测地线数量的极限分布。版权所有 © 2010 John Wiley & Sons, Ltd. J 图论 66:115‐136, 2011
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 dG(u, v) is at least dC(u, v)−e(n). Let ω(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) = logd−1logd−1n+ ω(n) and |C| = 2logd−1n+ O(ω(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. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011