On the size of hereditary classes of graphs (Q1328380): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Jennifer S. Zito / rank | |||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Property / author | |||
Property / author: Jennifer S. Zito / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1994.1027 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2081735788 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:43, 20 March 2024
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