DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2020.18

The Giant Component and 2-Core in Sparse Random Outerplanar Graphs

Authors: Mihyun Kang and Michael Missethan

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

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+O (n^{2/3}) and determine the typical order of the 2-core. In addition, we prove that if s=ω(n^{2/3}), with high probability every edge in A(n,m) belongs to at most one cycle.

Cite as

Mihyun Kang and Michael Missethan. The Giant Component and 2-Core in Sparse Random Outerplanar Graphs. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kang_et_al:LIPIcs.AofA.2020.18,
  author =	{Kang, Mihyun and Missethan, Michael},
  title =	{{The Giant Component and 2-Core in Sparse Random Outerplanar Graphs}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.18},
  URN =		{urn:nbn:de:0030-drops-120488},
  doi =		{10.4230/LIPIcs.AofA.2020.18},
  annote =	{Keywords: giant component, core, outerplanar graphs, singularity analysis}
}

Search Results

Documents authored by Missethan, Michael

The Giant Component and 2-Core in Sparse Random Outerplanar Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message