Application of an Extremal Result of Erdős and Gallai to the (n,k,t) Problem
oleh: Matt Noble, Peter Johnson, Dean Hoffman, Jessica McDonald
| Format: | Article |
|---|---|
| Diterbitkan: | Georgia Southern University 2017-01-01 |
Deskripsi
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.