AN IMPROVED UPPER BOUND ON THE LENGTH OF THE LONGEST CYCLE OF A SUPERCRITICAL RANDOM GRAPH

作者：Kemkes Graeme^*; Wormald Nicholas

来源：SIAM Journal on Discrete Mathematics, 2013, 27(1): 342-362.

DOI：10.1137/090766279

• random graph
• graph circumference
• cycle length

We improve Luczak%26apos;s upper bound on the length of the longest cycle in the random graph G(n, M) in the %26quot;supercritical phase,%26quot; 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 -%26gt; 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 -%26gt; 1, c - 1 = omega(n(-1/3)).

• 出版日期2013