𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Size of Hereditary Classes of Graphs

✍ Scribed by E.R Scheinerman; J Zito

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
912 KB
Volume
61
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

A hereditary property of graphs is a class of graphs which is closed under taking induced subgraphs. For a hereditary property (\mathscr{P}), let (\mathscr{P}{n}) denote the set of (\mathscr{P}) graphs on (n) labelled vertices. Clearly we have (0 \leqslant\left|\mathscr{P}{n}\right| \leqslant 2^{n(n-1) / 2}), but much more can be said. Our main results show that the growth of (\left|\mathscr{P}{n}\right|) is far from arbitrary and that certain growth rates are impossible. For example, for no property (\mathscr{P}) does one have (\left|\mathscr{P}{n}\right| \sim \log n . \quad 1994) Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

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

On easy and hard hereditary classes of g
On easy and hard hereditary classes of graphs with respect to the independent set problem
✍ Vladimir E. Alekseev πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 162 KB

In this paper we introduce the concept of a boundary class, which is a helpful tool for classiΓΏcation of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class X deΓΏned by a ΓΏnite set of forbidden induced subgraphs, the problem is NP-hard