Graphs with a small number of distinct induced subgraphs
type: Item
instance of: scholarly article
title: Graphs with a small number of distinct induced subgraphs
zbMATH Open document ID: 0681.05060
DOI: 10.1016/0012-365X(89)90074-5
author: Noga Alon
author: Béla Bollobás
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: Let G be a finite, simple and undirected graph and i(G) denotes the total number of isomorphism types of induced subgraphs of G. An induced subgraph of G is called trivial if it is either complete or independent and let t(G) denote the maximum number of vertices of such a trivial subgraph of G. By Hajnal the conjecture is formulated that if G is a graph on n vertices and \(i(G)=o(n^ 2)\), then \(t(G)=n-o(n)\) holds. The proof of this conjecture is the main result of the present paper (Theorem 1.1). This proof is a very lengthy one and requires two steps which consist of results on graphs with large trivial subgraphs and on graphs without large trivial subgraphs; the second step is the more difficult and the more important one regarding to Theorem 1.1. For \(i(G)\leq \epsilon n^ 2\) and \(t(G)\geq (n-\epsilon^*)\cdot n\) are given the two estimations \(\epsilon <10^{-21}\) and \(\epsilon^*=4\epsilon\) which are not optimal values and which can be improved. The conjecture was also proved in a stronger form by Erdős and Hajnal. Finally this paper contains some interesting unsolved problems.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4114691
zbMATH Keywords: isomorphism number
zbMATH Keywords: stable set
zbMATH Keywords: independent set of vertices
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: On generalized graphs
cites work: Q4074927
description: scientific article; zbMATH DE number 4114691