Theory and Applications of Graphs Theory and Applications of Graphs

Abstract

An extremal result about vertex covers, attributed by Hajnal [4] to Erd˝os and Gallai [2], is applied to prove the following: If n , k , and t are integers satisfying n ≥ k ≥ t ≥ 3 and k ≤ 2 t − 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.