Document Open Access Logo

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

Authors Mihyun Kang, Michael Missethan

PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.18.pdf
  • Filesize: 478 kB
  • 16 pages

Document Identifiers

Author Details

Mihyun Kang
  • Institute of Discrete Mathematics, Graz University of Technology, Austria
Michael Missethan
  • Institute of Discrete Mathematics, Graz University of Technology, Austria

Funding

  • Kang, Mihyun: Research supported by the Austrian Science Fund (FWF): I3747, W1230.
  • Missethan, Michael: Research supported by the Austrian Science Fund (FWF): W1230.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.AofA.2020.18

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
  • Mathematics of computing → Generating functions
Keywords
  • giant component
  • core
  • outerplanar graphs
  • singularity analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Béla Bollobás. The evolution of random graphs. Transactions of the American Mathematical Society, 286(1):257-274, 1984. Google Scholar
  2. Béla Bollobás. Random Graphs. Cambridge University Press, 2nd edition, 2001. Google Scholar
  3. V. E. Britikov. The structure of a random graph near a critical point. Diskretnaya Matematika, 1(3):121-128, 1989. Google Scholar
  4. Michael Drmota. Random Trees: An Interplay between Combinatorics and Probability. Springer-Verlag, 1st edition, 2009. Google Scholar
  5. Paul Erdős and Alfréd Rényi. On random graphs. I. Publicationes Mathematicae Debrecen, 6:290-297, 1959. Google Scholar
  6. Paul Erdős and Alfréd Rényi. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5:17-61, 1960. Google Scholar
  7. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Google Scholar
  8. Alan Frieze and Michał Karoński. Introduction to Random Graphs. Cambridge University Press, 2015. Google Scholar
  9. Svante Janson. Probability asymptotics: notes on notation. Institute Mittag-Leffler Report 12, 2011. Google Scholar
  10. Svante Janson, Donald E. Knuth, Tomasz Łuczak, and Boris Pittel. The birth of the giant component. Random Structures Algorithms, 4(3):231-358, 1993. Google Scholar
  11. Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random Graphs. Wiley, 2000. Google Scholar
  12. Mihyun Kang and Tomasz Łuczak. Two critical periods in the evolution of random planar graphs. Transactions of the American Mathematical Society, 364(8):4239-4265, 2012. Google Scholar
  13. Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel. Phase transitions in graphs on orientable surfaces. Random Structures and Algorithms, 2019. (to appear). Google Scholar
  14. Tomasz Łuczak. Component behavior near the critical point of the random graph process. Random Structures Algorithms, 1(3):287-310, 1990. Google Scholar
  15. Tomasz Łuczak and Boris Pittel. Components of random forests. Combinatorics, Probability and Computing, 1(1):35–52, 1992. Google Scholar
  16. Michael Missethan. Asymptotic properties of random outerplanar graphs. Master’s thesis, Graz University of Technology, 2019. URL: https://www.math.tugraz.at/~missethan/masters_thesis/arbeit.pdf.
  17. Lajos Takács. Counting forests. Discrete Mathematics, 84(3):323-326, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact