The Speed of Hereditary Properties of Graphs

József Balogh, Béla Bollobás, David Weinreich

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)131-156
Number of pages26
JournalJournal of Combinatorial Theory. Series B
Volume79
Issue number2
DOIs
StatePublished - Jul 2000
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The Speed of Hereditary Properties of Graphs'. Together they form a unique fingerprint.

Cite this