The number of cliques in graphs of given order and size

2007/10/11 by Vladimir Nikiforov, Nikiforov, Vladimir · 1 citation
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.0710.2305

openalex publication_date 2007/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let k_r(n,m) denote the minimum number of r-cliques in graphs with n vertices and m edges. For r=3,4 we give a lower bound on k_r(n,m) that approximates k_r(n,m) with an error smaller than n^r/(n²-2m). The solution is based on a constraint minimization of certain multilinear forms. In our proof, a combinatorial strategy is coupled with extensive analytical arguments.

Cited by

• On Domination Exponents for Pairs of Graphs

Related

• Cliques in graphs with bounded minimum degree
• Minimum Number of k-Cliques in Graphs with Bounded Independence Number
• The minimum number of 4-cliques in graphs with triangle-free complement
• A problem of Erdős on the minimum number of k-cliques
• On the maximum number of r-cliques in graphs free of complete r-partite subgraphs