A variation of a theorem by P\'osa
classification
🧮 math.CO
keywords
hamiltoniangraphboundcliquesmaximumnon-numberalmost
read the original abstract
A graph $G$ is $\ell$-hamiltonian if for any linear forest $F$ of $G$ with $\ell$ edges, $F$ can be extended to a hamiltonian cycle of $G$. We give a sharp upper bound for the maximum number of cliques of a fixed size in a non-$\ell$-hamiltonian graph. Furthermore, we prove stability for the bound: if a non-$\ell$-hamiltonian graph contains almost the maximum number of cliques, then it must be a subgraph of one of two examples.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.