Back to Search Start Over

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

Authors :
Matt Noble
Peter D. Johnson
Jessica McDonald
Dean G. Hoffman
Source :
Theory and Applications of Graphs, Vol 4, Iss 2 (2017)
Publication Year :
2017
Publisher :
Georgia Southern University, 2017.

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.

Details

Language :
English
ISSN :
24709859
Volume :
4
Issue :
2
Database :
OpenAIRE
Journal :
Theory and Applications of Graphs
Accession number :
edsair.doi.dedup.....f4ec0708b7b93801a7d523e72735a9dd