Geodesic cycles in random graphs

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.