On the maximum number of cliques in a graph

Details On the maximum number of cliques in a graph On the maximum number of cliques in a graph

2006-02-09

arxiv.org/abs/math/0602191v4

Graphs and Combinatorics 23(3):337-352, 2007

Mathematics

Combinatorics

To appear in "Graphs and Combinatorics"

Scientific paper

10.1007/s00373-007-0738-8

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)$.

Affiliated with

Also associated with

No associations

Rating

On the maximum number of cliques in a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the maximum number of cliques in a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the maximum number of cliques in a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-568858