pith. machine review for the scientific record. sign in

arxiv: 1804.05829 · v2 · pith:YQSSN425new · submitted 2018-04-16 · 🧮 math.CO

A variation of a theorem by P\'osa

classification 🧮 math.CO
keywords hamiltoniangraphboundcliquesmaximumnon-numberalmost
0
0 comments X
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.