An improved upper bound on the length of the longest cycle of a supercritical random graph

DOI10.1137/090766279MaRDI QIDQ5300499zbMATH OpenOpenAlexFDO

Authors Graeme Kemkes, Nicholas Wormald

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.3511

zbMATH Keywords

cycle lengthgraph circumferencerandom graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We improve Luczak's upper bounds on the length of the longest cycle in the random graph G(n,M) in the "supercritical phase" where M=n/2+s and s=o(n) but n^{2/3}=o(s). The new upper bound is (6.958+o(1))s^2/n with probability 1-o(1) as n approaches infinity. Letting c=1+2s/n, the equivalence between G(n,p) and G(n,M) implies the same result for G(n,p) where p=c/n, c approaching 1, c-1 = omega(n^{-1/3}).

Recommendations

• Cycles in a random graph near the critical point
• A scaling limit for the length of the longest cycle in a sparse random graph
• A note on long cycles in sparse random graphs
• scientific article; zbMATH DE number 3916307
• Cycle lengths in sparse random graphs

Cited in

(9)

• On the performance of the depth first search algorithm in supercritical random graphs
• Loose cores and cycles in random hypergraphs
• The longest cycle problem is polynomial on interval graphs
• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• Longest paths in random hypergraphs
• Cycle lengths in sparse random graphs
• Longest and shortest cycles in random planar graphs
• Heavy and light paths and Hamilton cycles
• Paths, cycles and sprinkling in random hypergraphs

This page was built for publication: An improved upper bound on the length of the longest cycle of a supercritical random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300499)