Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902999 | Discrete Mathematics | 2018 | 7 Pages |
Abstract
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âϵ)logdn with probability tending to one as nââ for d>1+ϵ with d=np 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±ϵ)logdn 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 a.a.s. not (1â2âϵ)logdn-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â«ln5nâ(lnlnn)2 which is obtained by Mitsche and PraÅat.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yuanzhi Li, Lingsheng Shi,