Geodesic cycles in random graphs
Geodesic cycles in random graphs
复制标题
随机图中的测地线循环
DOI：
10.1016/j.disc.2018.01.014
复制
发表时间：
2018-05
影响因子：
0.8
通讯作者：
Shi Lingsheng
中科院分区：
文献类型：
--
作者：
Li Yuanzhi;Shi Lingsheng
一个图中的圈是测地线的，如果圈上每对结点的距离与圈上限制的距离一致。本文证明了G（n，p）中的随机图有一个长度至少为（2− <$）logdn的测地圈，当d> 1+ n时，当n→∞时，概率趋于1，其中d= np，且每个小的正常数n为零.这个最长测地圈长度的下界几乎是紧的，因为对于足够大的d，随机图中巨分支的直径渐近几乎必然在（1± 1）log dn之内。取四个节点将测地圈分成四条长度大致相同的路径，意味着随机图中的巨分支aas不是（1 scin 2− 1）log d n-双曲。这个双曲性上的界改进了Narayan-Saniee-Tucci的超常数界，并且也接近于Mitsche和Prahanat得到的d ln 5 n scinln（ln ln n）2的精确值.
A cycle in a graph is geodesic if the distance of each pair of nodes on the cycle coincides with their distance restricted on the cycle. In this article, we prove that a random graph in G (n, p) has a geodesic cycle of length at least (2− ϵ) log d n with probability tending to one as n→∞ for d> 1+ ϵ with d= n p and each small positive constant ϵ. This lower bound on the length of the longest geodesic cycle is almost tight since the diameter of the giant component in the random graph is asymptotically almost surely within (1±ϵ) log d n for sufficiently large d. Taking four nodes that split the geodesic cycle into four paths of approximately the same length implies that the giant component in the random graph is aas not (1∕ 2− ϵ) log d n-hyperbolic. This bound on the hyperbolicity improves a super-constant bound of Narayan–Saniee–Tucci and also comes close to its exact value for d≫ ln 5 n∕(ln ln n) 2 which is obtained by Mitsche and Prałat.
登录
查看更多内容
DOI：
10.1016/0166-218x(91)90045-x
发表时间：
1991-02
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
T. Luczak
通讯作者：
T. Luczak
影响因子：
0.9
作者：
I. Benjamini;C. Hoppen;E. Ofek;P. Prałat;N. Wormald
通讯作者：
I. Benjamini;C. Hoppen;E. Ofek;P. Prałat;N. Wormald
影响因子：
1.1
作者：
B. Bollobás;A. Frieze;T. Fenner
通讯作者：
B. Bollobás;A. Frieze;T. Fenner
DOI：
10.1002/rsa.3240020405
发表时间：
1991-12
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
T. Luczak
通讯作者：
T. Luczak
影响因子：
1
作者：
Daniel Fernholz;V. Ramachandran
通讯作者：
Daniel Fernholz;V. Ramachandran