Graphs Having Small Number of Sizes on Induced k‐Subgraphs
Authors:
- Maria AxenovichMAMaria Axenovich
- József BaloghJBJózsef Balogh
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 21 (1) , 264-272
Abstract
Let $\ell$ be any positive integer, let n be a sufficiently large number, and let G be a graph on n vertices. Define, for any k, $\nu_k(G)= | \{ |E(H)| : H$ is an induced subgraph of G on k vertices$\} |$. We show that if there exists a k, $2\ell \leq k \leq n-2\ell$, such that $\nu_k(G) \le \ell$, then G has a complete or an empty subgraph on at least $n-\ell+1$ vertices and a homogeneous set of size at least $n-2\ell+2$. These results are sharp.
Keywords
This publication has 10 references indexed in Scilit:
- Hereditary Properties of Ordered Graphs2007
- Unavoidable Traces Of Set SystemsCombinatorica, 2005
- A jump to the bell number for hereditary graph propertiesJournal of Combinatorial Theory, Series B, 2005
- Disjoint representability of sets and their complementsJournal of Combinatorial Theory, Series B, 2005
- Erdős and Rényi ConjectureJournal of Combinatorial Theory, Series A, 1998
- On the number of distinct induced subgraphs of a graphDiscrete Mathematics, 1989
- Graphs with a small number of distinct induced subgraphsDiscrete Mathematics, 1989
- On the number of induced subgraphs of a random graphDiscrete Mathematics, 1987
- INDUCED SUBGRAPHS1984
- On a Problem of Formal LogicProceedings of the London Mathematical Society, 1930