The Sum of Degrees in Cliques

Source 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}.$$