An Improved Upper Bound on the Length of the Longest Cycle of a Supercritical Random Graph

DOI10.1137/090766279zbMath1267.05153arXiv0907.3511OpenAlexW2963604285MaRDI QIDQ5300499

Graeme Kemkes, Nicholas C. 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 lengthrandom graphgraph circumference

Mathematics Subject Classification ID

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

Related Items (7)

Cycle lengths in sparse random graphs ⋮ Heavy and light paths and Hamilton cycles ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Longest Paths in Random Hypergraphs ⋮ Asymptotic enumeration of strongly connected digraphs by vertices and edges ⋮ On the performance of the depth first search algorithm in supercritical random graphs ⋮ Loose cores and cycles 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