Mireille Bousquet-Mélou ; Kerstin Weller - Asymptotic properties of some minor-closed classes of graphs (conference version)

dmtcs:2327 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.2327
Asymptotic properties of some minor-closed classes of graphs (conference version)Article

Authors: Mireille Bousquet-Mélou ORCID1; Kerstin Weller 2

  • 1 Laboratoire Bordelais de Recherche en Informatique
  • 2 Department of Statistics [Oxford]

Let $\mathcal{A}$ be a minor-closed class of labelled graphs, and let $G_n$ be a random graph sampled uniformly from the set of n-vertex graphs of $\mathcal{A}$. When $n$ is large, what is the probability that $G_n$ is connected? How many components does it have? How large is its biggest component? Thanks to the work of McDiarmid and his collaborators, these questions are now solved when all excluded minors are 2-connected. Using exact enumeration, we study a collection of classes $\mathcal{A}$ excluding non-2-connected minors, and show that their asymptotic behaviour is sometimes rather different from the 2-connected case. This behaviour largely depends on the nature of the dominant singularity of the generating function $C(z)$ that counts connected graphs of $\mathcal{A}$. We classify our examples accordingly, thus taking a first step towards a classification of minor-closed classes of graphs. Furthermore, we investigate a parameter that has not received any attention in this context yet: the size of the root component. This follows non-gaussian limit laws (beta and gamma), and clearly deserves a systematic investigation.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: Asymptotic properties,Labelled graphs,Excluded minors,Enumeration,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 222 times.
This article's PDF has been downloaded 354 times.