LIPIcs.AofA.2020.18.pdf
- Filesize: 478 kB
- 16 pages
Document
The Giant Component and 2-Core in Sparse Random Outerplanar Graphs
Authors
-
Part of:
Volume:
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-10
Cite As Get 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)
0PDF Downloads
References
-
Béla Bollobás. The evolution of random graphs. Transactions of the American Mathematical Society, 286(1):257-274, 1984.
-
Béla Bollobás. Random Graphs. Cambridge University Press, 2nd edition, 2001.
-
V. E. Britikov. The structure of a random graph near a critical point. Diskretnaya Matematika, 1(3):121-128, 1989.
-
Michael Drmota. Random Trees: An Interplay between Combinatorics and Probability. Springer-Verlag, 1st edition, 2009.
-
Paul Erdős and Alfréd Rényi. On random graphs. I. Publicationes Mathematicae Debrecen, 6:290-297, 1959.
-
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.
-
Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
-
Alan Frieze and Michał Karoński. Introduction to Random Graphs. Cambridge University Press, 2015.
-
Svante Janson. Probability asymptotics: notes on notation. Institute Mittag-Leffler Report 12, 2011.
-
Svante Janson, Donald E. Knuth, Tomasz Łuczak, and Boris Pittel. The birth of the giant component. Random Structures Algorithms, 4(3):231-358, 1993.
-
Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random Graphs. Wiley, 2000.
-
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.
-
Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel. Phase transitions in graphs on orientable surfaces. Random Structures and Algorithms, 2019. (to appear).
-
Tomasz Łuczak. Component behavior near the critical point of the random graph process. Random Structures Algorithms, 1(3):287-310, 1990.
-
Tomasz Łuczak and Boris Pittel. Components of random forests. Combinatorics, Probability and Computing, 1(1):35–52, 1992.
- 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.
-
Lajos Takács. Counting forests. Discrete Mathematics, 84(3):323-326, 1990.