On degree power sum in $P_k$-free graphs

Abstract

Let $G$ be a graph on $n$ vertices with degree sequence $(d_1,d_2......d_n)$. For a real $p\ge 1$, let $D_p(G)={\sum }_{i=1}^n{d}_i^p$. A Turán-type problem of degree power sum was initiated by Caro and Yuster \cite{caro2000degpower}: determining the function $D_p(n,H) :=\max \{D_p(G): \text{$G$isan$n$-vertex$H$-free graph}\}$. They obtained some exact values for certain graphs $H$. For a path $P_k$, they mentioned that ``a close examination of the proof of Theorem 1.2 shows that the value of $n_0(k)$ in the statement of the theorem is $O(k^2)$", namely, they could show the $n$-vertex $P_k$-free graph with maximum degree power sum is $W_{n,k-1,\lfloor \frac{k}{2}\rfloor -1}=K_{\lfloor \frac{k}{2}\rfloor -1}\vee \left((n-\lceil \frac{k}{2}\rceil )K_1\cup K_{1+k-2\lfloor \frac{k}{2}\rfloor }\right)$ when $n\ge c{k}^2$ for some constant $c$. In this note, we improve their result to a linear size of $k$ by a different approach. The bound is tight up to a constant factor.

6 pages