Degree powers in graphs with forbidden subgraphs
The electronic journal of combinatorics, Tome 11 (2004) no. 1
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.
@article{10_37236_1795,
author = {B\'ela Bollob\'as and Vladimir Nikiforov},
title = {Degree powers in graphs with forbidden subgraphs},
journal = {The electronic journal of combinatorics},
year = {2004},
volume = {11},
number = {1},
doi = {10.37236/1795},
zbl = {1057.05045},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1795/}
}
Béla Bollobás; Vladimir Nikiforov. Degree powers in graphs with forbidden subgraphs. The electronic journal of combinatorics, Tome 11 (2004) no. 1. doi: 10.37236/1795
Cité par Sources :