Ferrero and Lesniak in 2018 found the maximum numbers of edges in -partite non-Hamiltonian graphs. Recently we found the maximum numbers of edges and -cliques in -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 -cliques in -free graphs that avoid one of the following properties: traceability, Hamiltonian-connectedness, -path Hamiltonicity, -Hamiltonicity, -Hamiltonian-connectedness, and -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 -cliques in -free graphs that avoid an arbitrary stable property that holds for sufficiently large complete graphs.

生成讲解博客的中文版本

生成AI智能校验的中文版本