A Turán Type Problem Concerning the Powers of the Degrees of a Graph (revised)

Abstract

For a graph $G$ whose degree sequence is $d_1,...,d_n$, and for a positive integer $p$, let $e_p(G)={\sum }_{i=1}^n{d}_i^p$. For a fixed graph $H$, let $t_p(n,H)$ denote the maximum value of $e_p(G)$ taken over all graphs with $n$ vertices that do not contain $H$ as a subgraph. Clearly, $t_1(n,H)$ is twice the Turán number of $H$. In this paper we consider the case $p>1$. For some graphs $H$ we obtain exact results, for some others we can obtain asymptotically tight upper and lower bounds, and many interesting cases remain open.

14 Pages