On the growth rate of minor-closed classes of graphs
| Autor: | Bernardi, Olivier, Noy, Marc, Welsh, Dominic |
|---|---|
| Přispěvatelé: | Centre de Recerca Matemàtica, Laboratoire de Mathématiques d'Orsay (LM-Orsay), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Universitat Politècnica de Catalunya [Barcelona] (UPC), Mathematical Institute [Oxford] (MI), University of Oxford [Oxford] |
| Rok vydání: | 2008 |
| Předmět: |
asymptotic enumeration
Grafs Teoria de 05C83 05C30 [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics AMS 05C83 05C30 Mathematics - Combinatorics growth constant growth rate 519.1 - Teoria general de l'anàlisi combinatòria. Teoria de grafs Combinatorics (math.CO) minor-closed class |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname |
| Popis: | The related article "Growth constants of minor-closed classes of graphs" (containing more results) is published in J. Combin. Theory, Ser B. Vol 100 (2010); A minor-closed class of graphs is a set of labelled graphs which is closed under isomorphism and under taking minors. For a minor-closed class $C$, we let $c_n$ be the number of graphs in $C$ which have $n$ vertices. A recent result of Norine et al. shows that for all minor-closed class $C$, there is a constant $r$ such that $c_n < r^n n!$. Our main results show that the growth rate of $c_n$ is far from arbitrary. For example, no minor-closed class $C$ has $c_n= r^{n+o(n)} n!$ with $0 < r < 1$ or $1 < r < \xi \approx 1.76$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|