Back to Search
Start Over
Application of an Extremal Result of Erdős and Gallai to the (n,k,t) Problem
- 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.
- Subjects :
- Erdős–Stone theorem
Erdős–Gallai theorem
Matching (graph theory)
Vertex cover
Turan's Theorem
(n
Theoretical Computer Science
Combinatorics
Computer Science::Discrete Mathematics
t) problem
Discrete Mathematics and Combinatorics
Turán graph
Mathematics
Discrete mathematics
Numerical Analysis
Mathematics::Combinatorics
matching
Turan graph
lcsh:Mathematics
Turán's theorem
lcsh:QA1-939
vertex cover
Erdos-Stone Theorem
independent set
Independent set
Subjects
Details
- Language :
- English
- ISSN :
- 24709859
- Volume :
- 4
- Issue :
- 2
- Database :
- OpenAIRE
- Journal :
- Theory and Applications of Graphs
- Accession number :
- edsair.doi.dedup.....f4ec0708b7b93801a7d523e72735a9dd