Extensions of the Erdős–Gallai theorem and Luo’s theorem

Source abstract

Abstract The famous Erdős–Gallai theorem on the Turán number of paths states that every graph with n vertices and m edges contains a path with at least (2 m )/ n edges. In this note, we first establish a simple but novel extension of the Erdős–Gallai theorem by proving that every graph G contains a path with at least $${{(s + 1){N_{s + 1}}(G)} \over {{N_s}(G)}} + s - 1$$ edges, where N j ( G ) denotes the number of j -cliques in G for 1 ≤ j ≤ ω(G) . We also construct a family of graphs which shows our extension improves the estimate given by the Erdős–Gallai theorem. Among applications, we show, for example, that the main results of [20], which are on the maximum possible number of s -cliques in an n -vertex graph without a path with ℓ vertices (and without cycles of length at least c ), can be easily deduced from this extension. Indeed, to prove these results, Luo [20] generalized a classical theorem of Kopylov and established a tight upper bound on the number of s -cliques in an n -vertex 2-connected graph with circumference less than c . We prove a similar result for an n -vertex 2-connected graph with circumference less than c and large minimum degree. We conclude this paper with an application of our results to a problem from spectral extremal graph theory on consecutive lengths of cycles in graphs.