On the size of hereditary classes of graphs (Q1328380): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Set OpenAlex properties.
 
(4 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Jennifer S. Zito / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Ralph J. Faudree / rank
Normal 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 / namelinks / 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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    hereditary
    0 references
    growth
    0 references
    0 references