On the maximum number of cliques in a graph

Research output: Contribution to journalArticleResearchpeer-review

38 Citations (Scopus)

Abstract

A 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 Δ; (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).
Original languageEnglish
Pages (from-to)337-352
Number of pages16
JournalGraphs and Combinatorics
Volume23
Issue number3
DOIs
Publication statusPublished - 2007
Externally publishedYes

Cite this