Many cliques with few edges

DOI10.37236/9550MaRDI QIDQ2223482zbMATH OpenOpenAlexFDO

Authors Rachel Kirsch, Andrew John Radcliffe

Publication date 29 January 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Recently Cutler and Radcliffe proved that the graph on $n$ vertices with maximum degree at most $r$ having the most cliques is a disjoint union of $lfloorn/(r+1)floor$ cliques of size $r+1$ together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with $m$ edges and maximum degree at most $r$, the graph that has the most cliques of size at least two is the disjoint union of $$ cliques of size $r+1$ together with the colex graph using the remainder of the edges.

Review text

Summary: Recently \textit{J. Cutler} and \textit{A. J. Radcliffe} [``The maximum number of complete subgraphs in a graph with given maximum degree, Preprint, \url{arXiv:1306.1803}] proved that the graph on \(n\) vertices with maximum degree at most \(r\) having the most cliques is a disjoint union of \(\lfloor n/(r+1)\rfloor\) cliques of size \(r+1\) together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with \(m\) edges and maximum degree at most \(r\), the graph that has the most cliques of size at least two is the disjoint union of \(\bigl\lfloor m \bigm/\binom{r+1}{2} \bigr\rfloor\) cliques of size \(r+1\) together with the colex graph using the remainder of the edges.

Recommendations

• Many triangles with few edges
• Many cliques with few edges and bounded maximum degree
• On the number of edge disjoint cliques in graphs of given size
• On the maximum number of cliques in a graph
• Many Cliques in Bounded-Degree Hypergraphs

Cites work

• Counting independent sets of a fixed size in graphs with a given minimum degree
• Face vectors of flag complexes
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Many \(T\) copies in \(H\)-free graphs
• Many triangles with few edges
• Maximizing the number of independent sets of a fixed size
• Shadows of colored complexes.
• The maximum number of complete subgraphs in a graph with given maximum degree
• The maximum number of complete subgraphs of fixed size in a graph with given maximum degree
• The maximum number of triangles in a graph of given maximum degree
• Two problems on independent sets in graphs

Cited in

(10)

• Many cliques with few edges and bounded maximum degree
• A simple proof of the Gan-Loh-Sudakov conjecture
• Counting cliques in 1-planar graphs
• Large cliques and independent sets all over the place
• How many cliques can a clique cover cover?
• Many Cliques in Bounded-Degree Hypergraphs
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• Exact results on generalized Erdős-Gallai problems
• Efficient enumeration of cliques in graphs with bounded maximum degree
• Very large cliques are easy to detect

This page was built for publication: Many cliques with few edges

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