On the maximum number of cliques in a graph

Abstract

A \emph{clique} is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with $n$ vertices and $m$ edges; (2) graphs with $n$ vertices, $m$ edges, and maximum degree $\Delta$; (3) $d$-degenerate graphs with $n$ vertices and $m$ edges; (4) planar graphs with $n$ vertices and $m$ edges; and (5) graphs with $n$ vertices and no $K_5$-minor or no $K_{3,3}$-minor. For example, the maximum number of cliques in a planar graph with $n$ vertices is $8(n-2)$.

To appear in "Graphs and Combinatorics"

Cited by in corpus (10)

• Rank-width and Tree-width of H-minor-free Graphs
• Subgraph densities in a surface
• The maximum number of cliques in a graph embedded in a surface
• Medians in median graphs and their cube complexes in linear time
• Parallel Algorithms for Finding Large Cliques in Sparse Graphs
• Supersaturation for subgraph counts
• Number of cliques in graphs with a forbidden subdivision
• Tree densities in sparse graph classes
• Planar graphs with the maximum number of induced 6-cycles
• Many cliques in bounded-degree hypergraphs