Extensions of the Erdős-Gallai theorem and Luo's theorem

DOI10.1017/S0963548319000269zbMATH Open1436.05053arXiv1801.09981MaRDI QIDQ5222574FDOQ5222574

Authors: Bo Ning, Xing Peng 

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: The famous ErdH{o}s-Gallai Theorem on the Tur'an number of paths states that every graph with $n$ vertices and $m$ edges contains a path with at least $frac2mn$ edges. In this note, we first establish a simple but novel extension of the ErdH{o}s-Gallai Theorem by proving that every graph $G$ contains a path with at least $frac(s+1)N_{s+1}(G)N_s(G)+s-1$ edges, where $N_j(G)$ denotes the number of $j$-cliques in $G$ for $1leqjleqomega(G)$. We also construct a family of graphs which shows our extension improves the estimate given by ErdH{o}s-Gallai Theorem. Among applications, we show, for example, that the main results of cite{L17}, which are on the maximum possible number of $s$-cliques in an $n$-vertex graph without a path with $l$ vertices (and without cycles of length at least $c$), can be easily deduced from this extension. Indeed, to prove these results, Luo cite{L17} 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.

Full work available at URL: https://arxiv.org/abs/1801.09981

Recommendations

• The maximum number of cliques in graphs without long cycles
• Stability in the Erdős-Gallai theorems on cycles and paths
• Hypergraph extensions of the Erdős-Gallai theorem
• Stability in the Erdős-Gallai theorem on cycles and paths. II
• Hypergraph extensions of the Erdős-Gallai theorem

zbMATH Keywords

Turán number of paths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cites Work

• On the number of pentagons in triangle-free graphs
• On maximal paths and circuits of graphs
• The history of degenerate (bipartite) extremal graph problems
• On the maximum number of five-cycles in a triangle-free graph
• Path Ramsey numbers in multicolorings
• Title not available (Why is that?)
• Maximal circuits of graphs. I
• Long cycles in subgraphs with prescribed minimum degree
• Large cycles in graphs
• On maximal circuits in directed graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A spectral condition for odd cycles in graphs
• Sufficient Conditions for Circuits in Graphs^†
• Long cycles and the codiameter of a graph. I
• Pentagons vs. triangles
• Cycles in weighted graphs
• Many \(T\) copies in \(H\)-free graphs
• Cycles in 2-connected graphs
• On the maximum size of connected hypergraphs without a path of given length
• A note on the maximum number of triangles in a C₅‐free graph

Cited In (27)

• extremal aspects of the Erdős-Gallai-Tuza conjecture
• The maximum number of copies of \(K_{r,s}\) in graphs without long cycles or paths
• Stability of Woodall's theorem and spectral conditions for large cycles
• Generalized Turán number of even linear forests
• Further results on the generalized Turán number of spanning linear forests
• Generalized Turán number for linear forests
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• Eigenvalues and cycles of consecutive lengths
• Hypergraph extensions of the Erdős-Gallai theorem
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• A spectral condition for the existence of a pentagon in non-bipartite graphs
• The maximum number of cliques in graphs with prescribed order, circumference and minimum degree
• Maximizing the number of cliques in graphs with given matching number
• The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number
• A spectral condition for odd cycles in non-bipartite graphs
• The maximum number of cliques in graphs with bounded odd circumference
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• The generalized Turán number of spanning linear forests
• Spectral extrema of graphs: forbidden hexagon
• The maximum number of cliques in hypergraphs without large matchings
• A localized approach for Turán number of long cycles
• Spectral radius, edge-disjoint cycles and cycles of the same length
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Revisit of Erdős-Gallai's theorem on the circumference of a graph
• Exact results on generalized Erdős-Gallai problems
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs
• Ordering \(Q\)-indices of graphs: given size and circumference

This page was built for publication: Extensions of the Erdős-Gallai theorem and Luo's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222574)