Graphs with most number of three point induced connected subgraphs

✍ Scribed by F.T. Boesch; X. Li; J. Rodriguez

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 678 KB
Volume: 59
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(93)e0155-r

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Graphs with a small number of distinct i

Graphs with a small number of distinct induced subgraphs

✍ Noga Alon; Béla Bollobás 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 514 KB

Let G be a graph on n vertices. We show that if the total number of isomorphism types of induced subgraphs of G is at most &II', where E < lo-\*', then either G or its complement contain an independent set on at least (1 -4e)n vertices. This settles a problem of Erdiis and Hajnal.