The giant component and 2-core in sparse random outerplanar graphs

DOI10.4230/LIPICS.AOFA.2020.18MaRDI QIDQ6339565arXivFDO

Authors Mihyun Kang, Michael Missethan

Publication date 28 April 2020

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.AOFA.2020.18

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

arXiv classification

math.CO

Abstract: Let $A(n,m)$ be a graph chosen uniformly at random from the class of all vertex-labelled outerplanar graphs with $n$ vertices and $m$ edges. We consider $A(n,m)$ in the sparse regime when $m=n/2+s$ for $s=o(n)$. We show that with high probability the giant component in $A(n,m)$ emerges at $m=n/2+Oleft(n^{2/3}ight)$ and determine the typical order of the 2-core. In addition, we prove that if $s=omegaleft(n^{2/3}ight)$, with high probability every edge in $A(n,m)$ belongs to at most one cycle.

This page was built for publication: The giant component and 2-core in sparse random outerplanar graphs

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