On the size of hereditary classes of graphs (Q1328380)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the size of hereditary classes of graphs |
scientific article |
Statements
On the size of hereditary classes of graphs (English)
0 references
29 August 1994
0 references
For a hereditary property \(\mathcal P\) (closed under taking induced subgraphs), let \({\mathcal P}_ n\) denote the \(\mathcal P\) graphs on \(n\) labelled vertices. The growth of \(| {\mathcal P}_ n |\) is studied, and it is shown that certain growth rates are not possible. For example it is shown that if \(\mathcal P\) is a hereditary property such that \(| {\mathcal P}_ n |\) is bounded, then in fact \(| {\mathcal P}_ n | = 0\), 1 or 2. More generally, it is shown that either \(| {\mathcal P}_ n |\) is a constant, \(| {\mathcal P}_ n |\) grows polynomially \((p_ 1(n) \leq | {\mathcal P}_ n| \leq p_ 2(n))\), \(| {\mathcal P}_ n |\) grows exponentially \((c^ n_ 1 \leq | {\mathcal P}_ n | \leq c^ n_ 2\) for \(1 < c_ 1 \leq c_ 2\) and for \(n\) sufficiently large), \(| {\mathcal P}_ n|\) grows factorially \((n^{c_ 1 n} \leq | {\mathcal P}_ n | \leq n^{c_ 2 n}\) for \(0 < c_ 1 \leq c_ 2\) and for \(n\) sufficiently large), or \(| {\mathcal P}_ n|\) grows superfactorially.
0 references
hereditary
0 references
growth
0 references