Given a property P of graphs, write Pn for the set of graphs with vertex set [n] having property P. The growth or speed of a property P can be discussed in terms of the values of Pn. For properties with Pn<nn hereditary properties are surprisingly well determined by their speeds. Sharpening results of E. R. Scheinerman and J. Zito (1994, J. Combin. Theory Ser. B61, 16-39), we prove numerous results about the possible functions Pn and describe in detail the properties exhibiting each type of growth. We also list minimal properties exhibiting each type of growth.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics