Degree Powers in Graphs with a Forbidden Even Cycle

Vladimir Nikiforov

Abstract


Let $C_{l}$ denote the cycle of length $l$. For $p\geq2$ and integer $k\geq1$, we prove that the function $$ \phi\left( k,p,n\right) =\max_G\left\{ \sum_{u\in V\left( G\right) } d^{p}\left( u\right)\right\} $$ (where the maximum is over graphs $G$ of order $n$ containing no $C_{2k+2}$) satisfies $\phi\left( k,p,n\right) =kn^{p}\left( 1+o\left( 1\right) \right)$. This settles a conjecture of Caro and Yuster. Our proof is based on a new sufficient condition for long paths.


Full Text: PDF