Application of an Extremal Result of Erdős and Gallai to the (n,k,t) Problem

Abstract

An extremal result about vertex covers, attributed by Hajnal to Erdős and Gallai, is applied to prove the following: If n, k, and t are integers satisfying n ≥ k ≥ t ≥ 3 and k ≤ 2t - 2, and G is a graph with the minimum number of edges among graphs on n vertices with the property that every induced subgraph on k vertices contains a complete subgraph on t vertices, then every component of G is complete.

Keywords

• vertex cover
• independent set
• matching
• (n
• k
• t) problem
• Erdos-Stone Theorem
• Turan's Theorem
• Turan graph