Graphs having small number of sizes on induced k-subgraphs

Maria Axenovich, József Balogh

Research output: Contribution to journalArticlepeer-review

Abstract

Let ℓ be any positive integer, let n be a sufficiently large number, and let G be a graph on n vertices. Define, for any k, vk(G) = |{E(H)| : H is an induced subgraph of G on k vertices}|. We show that if there exists a k, 2ℓ ≤ k ≤ n - 2ℓ, such that vk(G) ≤ ℓ, then G has a complete or an empty subgraph on at least n - ℓ + 1 vertices and a homogeneous set of size at least n - 2ℓ + 2. These results are sharp.

Original languageEnglish (US)
Pages (from-to)264-272
Number of pages9
JournalSIAM Journal on Discrete Mathematics
Volume21
Issue number1
DOIs
StatePublished - 2007

Keywords

  • Homogeneous sets
  • Induced subgraphs
  • Reconstruction

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Graphs having small number of sizes on induced k-subgraphs'. Together they form a unique fingerprint.

Cite this