The Sum of Degrees in Cliques

Abstract

For every graph $G,$ let $$ \Delta_{r}\left(G\right) =\max\left\{ \sum_{u\in R}d\left( u\right) :R\hbox{ is an }r\hbox{-clique of }G\right\} $$ and let $\Delta_{r}\left( n,m\right) $ be the minimum of $\Delta_{r}\left( G\right)$ taken over all graphs of order $n$ and size $m$. Write $t_{r}\left( n\right) $ for the size of the $r$-chromatic Turán graph of order $n$.

Improving earlier results of Edwards and Faudree, we show that for every $r\geq2,$ if $m\geq t_{r}\left( n\right)$, then $$ \Delta_{r}\left( n,m\right) \geq\frac{2rm}{n},\qquad(1) $$ as conjectured by Bollobás and Erdős.

It is known that inequality (1) fails for $m < t_{r}\left(n\right)$. However, we show that for every $\varepsilon>0,$ there is $\delta>0$ such that if $m>t_{r}\left( n\right) -\delta n^{2}$ then $$ \Delta_{r}\left( n,m\right) \geq\left( 1-\varepsilon\right) \frac{2rm}{n}. $$