The sum of degrees in cliques

Béla Bollobás ; Vladimir Nikiforov

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

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

Détail

DOI : 10.37236/1988

Classification : 05C35
Mots-clés : Turán graph