Physical Sciences and Mathematics Commons^™

Application Of An Extremal Result Of Erdős And Gallai To The (N,K,T) Problem, Matt Noble, Peter Johnson, Dean Hoffman, Jessica Mcdonald

Theory and Applications of Graphs

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.