Degree Powers in Graphs with Forbidden Subgraphs

  • Béla Bollobás
  • Vladimir Nikiforov

Abstract

For every real $p>0$ and simple graph $G,$ set $$ f\left( p,G\right) =\sum_{u\in V\left( G\right) }d^{p}\left( u\right) , $$ and let $\phi\left( r,p,n\right) $ be the maximum of $f\left( p,G\right) $ taken over all $K_{r+1}$-free graphs $G$ of order $n.$ We prove that, if $0 < p < r,$ then$$ \phi\left( r,p,n\right) =f\left( p,T_{r}\left( n\right) \right) , $$ where $T_{r}\left( n\right) $ is the $r$-partite Turan graph of order $n$. For every $p\geq r+\left\lceil \sqrt{2r}\right\rceil $ and $n$ large, we show that$$ \phi\left( p,n,r\right) >\left( 1+\varepsilon\right) f\left( p,T_{r}\left( n\right) \right) $$ for some $\varepsilon=\varepsilon\left( r\right) >0.$

Our results settle two conjectures of Caro and Yuster.

Published
2004-06-25
Article Number
R42