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 $\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.
@article{10_37236_9550,
author = {Rachel Kirsch and A. J. Radcliffe},
title = {Many cliques with few edges},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/9550},
zbl = {1456.05080},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9550/}
}
TY - JOUR
AU - Rachel Kirsch
AU - A. J. Radcliffe
TI - Many cliques with few edges
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9550/
DO - 10.37236/9550
ID - 10_37236_9550
ER -
%0 Journal Article
%A Rachel Kirsch
%A A. J. Radcliffe
%T Many cliques with few edges
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9550/
%R 10.37236/9550
%F 10_37236_9550
Rachel Kirsch; A. J. Radcliffe. Many cliques with few edges. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9550
