Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903910 | Journal of Combinatorial Theory, Series B | 2018 | 8 Pages |
Abstract
The ErdÅs-Gallai Theorem states that for kâ¥3 every graph on n vertices with more than 12(kâ1)(nâ1) edges contains a cycle of length at least k. Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples Hn,k,t and Hn,k,2. In this note, we generalize the result of Kopylov to bound the number of s-cliques in a graph with circumference less than k. Furthermore, we show that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, we obtain the extremal number of s-cliques in a graph with no path on k-vertices.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ruth Luo,