Maximizing the number of cliques in Kr+1-free graphs with forbidden properties
Abstract
Ferrero and Lesniak in 2018 found the maximum numbers of edges in r-partite non-Hamiltonian graphs. Recently we found the maximum numbers of edges and t-cliques in Kr+1-free graphs (1) that are not Hamiltonian or (2) that satisfy a condition on low-degree vertices related to Pósa's theorem. Applying theorem (2), here we extend theorem (1) from Hamiltonicity to other properties. We determine the maximum numbers of edges and t-cliques in Kr+1-free graphs that avoid one of the following properties: traceability, Hamiltonian-connectedness, k-path Hamiltonicity, k-Hamiltonicity, k-Hamiltonian-connectedness, and k-connectedness. We find all extremal graphs having the maximum numbers of edges. On the way, we prove upper bounds on the numbers of edges and t-cliques in Kr+1-free graphs that avoid an arbitrary stable property that holds for sufficiently large complete graphs.
Related
- Trace-minimal graphs maximizing the number of spanning trees
- Turán number of three disjoint cliques of arbitrary sizes
- Normal approximation for subgraph counts in random intersection graphs: the case of cliques
- Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
- First Subconstituents of Orthogonal Graphs in Even Characteristic:Automorphisms, Cliques, Cores, and Binary Triple Transitivity
BibTeX
@misc{dawkins2026maximizing,
title = {{Maximizing the number of cliques in $K_r+1$-free graphs with forbidden properties}},
author = {Aleyah Dawkins and Rachel Kirsch},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25196},
eprint = {2609.25196},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25196},
}
RIS
TY - UNPB
TI - Maximizing the number of cliques in K_r+1-free graphs with forbidden properties
AU - Aleyah Dawkins
AU - Rachel Kirsch
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.25196
UR - https://arxiv.org/abs/2609.25196
AB - Ferrero and Lesniak in 2018 found the maximum numbers of edges in r-partite non-Hamiltonian graphs. Recently we found the maximum numbers of edges and t-cliques in K_r+1-free graphs (1) that are not Hamiltonian or (2) that satisfy a condition on low-degree vertices related to Pósa's theorem. Applying theorem (2), here we extend theorem (1) from Hamiltonicity to other properties. We determine the maximum numbers of edges and t-cliques in K_r+1-free graphs that avoid one of the following properties: traceability, Hamiltonian-connectedness, k-path Hamiltonicity, k-Hamiltonicity, k-Hamiltonian-connectedness, and k-connectedness. We find all extremal graphs having the maximum numbers of edges. On the way, we prove upper bounds on the numbers of edges and t-cliques in K_r+1-free graphs that avoid an arbitrary stable property that holds for sufficiently large complete graphs.
ER -