Degree powers in graphs with a forbidden forest

Abstract

Given a positive integer $p$ and a graph $G$ with degree sequence $d_1,\dots ,d_n$, we define $e_p(G)={\sum }_{i=1}^n{d}_i^p$. Caro and Yuster introduced a Turán-type problem for $e_p(G)$: Given a positive integer $p$ and a graph $H$, determine the function $e{x}_p(n,H)$, which is the maximum value of $e_p(G)$ taken over all graphs $G$ on $n$ vertices that do not contain $H$ as a subgraph. Clearly, $e{x}_1(n,H)=2ex(n,H)$, where $ex(n,H)$ denotes the classical Turán number. Caro and Yuster determined the function $e{x}_p(n,P_{\ell })$ for sufficiently large $n$, where $p\ge 2$ and $P_{\ell }$ denotes the path on $\ell$ vertices. In this paper, we generalise this result and determine $e{x}_p(n,F)$ for sufficiently large $n$, where $p\ge 2$ and $F$ is a linear forest. We also determine $e{x}_p(n,S)$, where $S$ is a star forest; and $e{x}_p(n,B)$, where $B$ is a broom graph with diameter at most six.

24 pages, 2 figures