On the maximum number of cliques in a graph

DOI10.1007/S00373-007-0738-8zbMATH Open1122.05048arXivmath/0602191OpenAlexW3124913715MaRDI QIDQ995772FDOQ995772

David R. Wood

Publication date: 10 September 2007

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

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

Recommendations

• Counting cliques in 1-planar graphs
• scientific article; zbMATH DE number 861332
• On the maximum number of cliques in a graph embedded in a surface
• Cliques in graphs excluding a complete graph minor
• An upper bound on the number of cliques in a graph

zbMATH Keywords

degeneracyextremal graph theorycliquegraph minorplanar graphcomplete subgraphTurán's theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph minors (05C83)

Cites Work

• A partial k-arboretum of graphs with bounded treewidth
• The extremal function for complete minors
• Title not available (Why is that?)
• An extremal function for contractions of graphs
• On cliques in graphs
• Ramsey-Turán theory
• Lower bounds on the number of triangles in a graph
• Cliques in random graphs
• Title not available (Why is that?)
• The maximum number of triangles in a \(K_4\)-free graph
• A new Turán-type theorem for cliques in graphs
• Proper minor-closed families are small
• Title not available (Why is that?)
• Title not available (Why is that?)
• On cliques in graphs
• Title not available (Why is that?)
• Maximal independent sets in graphs with at mostr cycles
• On Hadwiger's number---A problem of the Nordhaus-Gaddum type
• The Number of Maximal Independent Sets in a Tree
• On the number of complete subgraphs and circuits contained in graphs
• On complete subgraphs of \(r\)-chromatic graphs
• The maximum number of q-cliques in a graph with no p-clique
• A generalization of a theorem of Turán
• Maximal and maximum independent sets in graphs with at mostr cycles
• Title not available (Why is that?)
• An upper bound on the number of cliques in a graph
• The number of maximum independent sets in graphs
• Title not available (Why is that?)
• Bounds on the number of complete subgraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Clique graphs of packed graphs
• Limit theorems for complete subgraphs of random graphs
• A new proof of the Fisher-Ryan bounds for the number of cliques of a graph
• Title not available (Why is that?)
• On clique-extremal (p,q)-graphs
• Title not available (Why is that?)
• Connectivity, graph minors, and subgraph multiplicity
• Title not available (Why is that?)
• On the Number of Complete Subgraphs of a Graph
• On the number of complete subgraphs and circuits in a graph
• On cliques in graphs

Cited In (44)

• Supersaturation for subgraph counts
• Generalized planar Turán numbers
• Counting cliques in 1-planar graphs
• Number of Cliques in Graphs with a Forbidden Subdivision
• The sum of degrees in cliques
• Many triangles with few edges
• On the clique number of the square of a line graph and its relation to maximum degree of the line graph
• Title not available (Why is that?)
• On graphs having prescribed clique number, chromatic number, and maximum degree
• Kernelization using structural parameters on sparse graph classes
• Cliques with maximum/minimum edge neighborhood and neighborhood density
• Clique numbers of graphs
• Tree densities in sparse graph classes
• Many cliques with few edges and bounded maximum degree
• Subgraph densities in a surface
• Independent sets in graphs
• Cliques in graphs excluding a complete graph minor
• A localized approach to generalized Turán problems
• Rank-width and tree-width of \(H\)-minor-free graphs
• On supersaturation and stability for generalized Turán problems
• An extended depth-first search algorithm for optimal triangulation of Bayesian networks
• The maximum number of cliques in graphs without long cycles
• The maximum number of 3- and 4-cliques within a planar maximally filtered graph
• On the maximum number of cliques in a graph embedded in a surface
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Planar graphs with the maximum number of induced 6-cycles
• Title not available (Why is that?)
• The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
• The maximum number of paths of length three in a planar graph
• Title not available (Why is that?)
• The maximum clique problem in multiple interval graphs
• The maximum number of cliques in dense graphs
• A note on Turán's theorem
• The maximum number of pentagons in a planar graph
• Homomorphisms into loop-threshold graphs
• Many Cliques in Bounded-Degree Hypergraphs
• The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
• Enumeration aspects of maximal cliques and bicliques
• On the number of cliques in graphs with a forbidden minor
• The maximum number of complete subgraphs in a graph with given maximum degree
• Title not available (Why is that?)
• Local planar domination revisited
• Medians in median graphs and their cube complexes in linear time
• The Hosoya index and the Merrifield-Simmons index

This page was built for publication: On the maximum number of cliques in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q995772)