Maximizing the number of cliques in -free graphs with forbidden properties
En palabras de los autores
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\'{o}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.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 30 pages. arXiv:2310.11452v4 has been split into two papers, with the first on Hamiltonicity and chorded pancyclicity at arXiv:2310.11452v5, and all other properties in this second paper