Linear circumference conjecture for random cubic planar multigraphs
Linear circumference conjecture for random cubic planar multigraphs
Let be a graph chosen uniformly at random from the class of all cubic planar multigraphs on vertex set . Its circumference is the length of its longest cycle.
Linear circumference conjecture.
Random cubic planar multigraphs cannot have Hamiltonian cycles because linearly many vertices have an attached loop, but the conjecture asserts that they nevertheless have cycles of linear length with high probability. This would determine the asymptotic order of the circumference and is used to obtain the corresponding weakly supercritical result for random planar graphs.
Sources & referencesView supporting material
Primary source
Mihyun Kang and Michael Missethan, “Longest and shortest cycles in random planar graphs”, arXiv:2006.09697 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.