The maximum number of cliques in graphs without long cycles

DOI10.1016/J.JCTB.2017.08.005zbMath1375.05147arXiv1701.07472OpenAlexW2963861976MaRDI QIDQ1682216

Ruth Luo

Publication date: 28 November 2017

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The ErdH{o}s--Gallai Theorem states that for $kgeq3$ every graph on $n$ vertices with more than $frac12(k-1)(n-1)$ edges contains a cycle of length at least $k$. Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples $H_{n,k,t}$ and $H_{n,k,2}$. In this note, we generalize the result of Kopylov to bound the number of $s$-cliques in a graph with circumference less than $k$. Furthermore, we show that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, we obtain the extremal number of $s$-cliques in a graph with no path on $k$-vertices.

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

zbMATH Keywords

pathscyclesTurán problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On 3-uniform hypergraphs without a cycle of a given length
• On the maximum number of five-cycles in a triangle-free graph
• Pentagons vs. triangles
• On maximal circuits in directed graphs
• Path Ramsey numbers in multicolorings
• Sudden emergence of a giant \(k\)-core in a random graph
• On the number of pentagons in triangle-free graphs
• The Maximum Number of Triangles in C_2k+1-Free Graphs
• On maximal paths and circuits of graphs
• Maximal circuits of graphs. I
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Many \(T\) copies in \(H\)-free graphs

Related Items (44)

Paths of length three are \(K_{r+1}\)-Turán-good ⋮ Subgraph densities in a surface ⋮ Tree densities in sparse graph classes ⋮ Generalized rainbow Turán problems ⋮ Generalized Turán number for linear forests ⋮ On generalized Turán number of two disjoint cliques ⋮ A note on the Tur\'an number of a Berge odd cycle ⋮ Complete subgraphs in connected graphs and its application to spectral moment ⋮ Generalized planar Turán numbers ⋮ The maximum number of triangles in \(F_k\)-free graphs ⋮ Ordering \(Q\)-indices of graphs: given size and circumference ⋮ The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number ⋮ A variation of a theorem by Pósa ⋮ Stability version of Dirac's theorem and its applications for generalized Turán problems ⋮ The Number of Cliques in Graphs Covered by Long Cycles ⋮ Maximum cliques in a graph without disjoint given subgraph ⋮ The maximum number of cliques in graphs with prescribed order, circumference and minimum degree ⋮ The maximum number of cliques in hypergraphs without large matchings ⋮ Triangles in graphs without bipartite suspensions ⋮ A Dirac-type theorem for uniform hypergraphs ⋮ The maximum number of copies of \(K_{r,s}\) in graphs without long cycles or paths ⋮ The maximum number of cliques in graphs with bounded odd circumference ⋮ Maximizing the number of cliques in graphs with given matching number ⋮ Some sharp results on the generalized Turán numbers ⋮ On the maximum size of connected hypergraphs without a path of given length ⋮ Many H-Copies in Graphs with a Forbidden Tree ⋮ Exact generalized Turán numbers for even linear forests ⋮ A stability result of the Pósa lemma ⋮ The constructor-blocker game ⋮ Exact results on generalized Erdős-Gallai problems ⋮ A note on the stability results of the number of cliques in graphs with given matching number ⋮ Generalized Turán number of even linear forests ⋮ A localized approach to generalized Turán problems ⋮ The maximum number of \(P_\ell\) copies in \(P_k\)-free graphs ⋮ On generalized Turán numbers of intersecting cliques ⋮ A localized approach for Turán number of long cycles ⋮ The shifting method and generalized Turán number of matchings ⋮ Avoiding long Berge cycles ⋮ Asymptotics for the Turán number of Berge-\(K_{2,t}\) ⋮ Berge cycles in non-uniform hypergraphs ⋮ On 2-connected hypergraphs with no long cycles ⋮ Further results on the generalized Turán number of spanning linear forests ⋮ The generalized Turán number of spanning linear forests ⋮ Supersaturation for subgraph counts

This page was built for publication: The maximum number of cliques in graphs without long cycles