𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Speed of Hereditary Properties of Graphs

✍ Scribed by József Balogh; Béla Bollobás; David Weinreich

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
217 KB
Volume
79
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

Given a property P of graphs, write P n 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 |P n |. For properties with |P n | <n n hereditary properties are surprisingly well determined by their speeds. Sharpening results of E. R. Scheinerman and J. Zito (1994, J. Combin. Theory Ser. B 61, 16 39), we prove numerous results about the possible functions |P n | and describe in detail the properties exhibiting each type of growth. We also list minimal properties exhibiting each type of growth.

📜 SIMILAR VOLUMES

Hereditary properties of combinatorial s
Hereditary properties of combinatorial structures: Posets and oriented graphs
✍ József Balogh; Béla Bollobás; Robert Morris 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract A hereditary property of combinatorial structures is a collection of structures (e.g., graphs, posets) which is closed under isomorphism, closed under taking induced substructures (e.g., induced subgraphs), and contains arbitrarily large structures. Given a property $\cal {P}$, we write

On the structure of hereditary classes o
On the structure of hereditary classes of graphs
✍ Edward R. Scheinerman 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 333 KB 👁 1 views

A class of graphs is hereditary if it is closed under taking induced subgraphs. Classes associated with graph representations have "composition sequences" and we show that this concept is equivalent to a notion of "amalgamation" which generalizes disjoint union of graphs. We also discuss how general

Additive and hereditary properties of gr
Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors
✍ Mih�k, Peter; Semani?in, Gabriel; Vasky, Roman 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB 👁 2 views

A hereditary property of graphs is any class of graphs closed under isomorphism and subgraphs. Let P 1 , P 2 , . . . , P n be hereditary properties of graphs. We say that a graph G has property P 1 . . , V n such that the subgraph of G induced by V i belongs to P i ; i = 1, 2, . . . , n. A heredita

A characterization of 3-Steiner distance
A characterization of 3-Steiner distance hereditary graphs
✍ Day, D. P.; Oellermann, Ortrud R.; Swart, Henda C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 1 views

Let G be a connected graph and S ⊆ V (G). Then, the Steiner distance of S in G, denoted by d G (S), is the smallest number of edges in a connected subgraph of G that contains . Some general properties about the cycle structure of k-Steiner distance hereditary graphs are established. These are then

Generalized Pigeonhole Properties of Gra
Generalized Pigeonhole Properties of Graphs and Oriented Graphs
✍ Anthony Bonato; Peter J Cameron; Dejan Delić; Stéphan Thomassé 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic to A. The P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied