Exact results on generalized Erdős-Gallai problems
Preprint
Abstract
Generalized Tur\'an problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- On the maximum size of connected hypergraphs without a path of given lengthDiscrete Mathematics, 2018
- On 3-uniform hypergraphs without a cycle of a given lengthDiscrete Applied Mathematics, 2017
- The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum DegreeJournal of Graph Theory, 2016
- A New Method for Enumerating Independent Sets of a Fixed Size in General GraphsJournal of Graph Theory, 2015
- Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum DegreeJournal of Graph Theory, 2013
- Two problems on independent sets in graphsDiscrete Mathematics, 2011
- Face vectors of flag complexesIsrael Journal of Mathematics, 2008
- Maximal circuits of graphs. IActa Mathematica Hungarica, 1976
- Path Ramsey numbers in multicoloringsJournal of Combinatorial Theory, Series B, 1975
- On maximal paths and circuits of graphsActa Mathematica Hungarica, 1959