On the maximum number of cliques in a graph

DOI10.1007/S00373-007-0738-8MaRDI QIDQ995772zbMATH OpenOpenAlexFDO

Authors David R. Wood

Publication date 10 September 2007

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

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

zbMATH Keywords

degeneracyextremal graph theorycliquegraph minorplanar graphcomplete subgraphTurán's theorem

Mathematics Subject Classification ID

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

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

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

Cites work

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

Cited in

(45)

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

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)