Extremal results on degree powers in some classes of graphs

Abstract

Let $G$ be a simple graph of order $n$ with degree sequence $(d_1,d_2,\cdots ,d_n)$. For an integer $p>1$, let $e_p(G)={\sum }_{i=1}^n{d}_i^p$ and let $e{x}_p(n,H)$ be the maximum value of $e_p(G)$ among all graphs with $n$ vertices that do not contain $H$ as a subgraph (known as $H$-free graphs). Caro and Yuster proposed the problem of determining the exact value of $e{x}_2(n,C_4)$, where $C_4$ is the cycle of length $4$. In this paper, we show that if $G$ is a $C_4$-free graph having $n\ge 4$ vertices and $m\le \lfloor 3(n-1)/2\rfloor$ edges and no isolated vertices, then $e_p(G)\le e_p(F_n)$, with equality if and only if $G$ is the friendship graph $F_n$. This yields that for $n\ge 4$, $e{x}_p(n,{\mathcal{C}}^{\ast })=e_p(F_n)$ and $F_n$ is the unique extremal graph, which is an improved complement of Caro and Yuster's result on $e{x}_p(n,{\mathcal{C}}^{\ast })$, where ${\mathcal{C}}^{\ast }$ denotes the family of cycles of even lengths. We also determine the maximum value of $e_p(\cdot )$ among all minimally $t$-(edge)-connected graphs with small $t$ or among all $k$-degenerate graphs, and characterize the corresponding extremal graphs. A key tool in our approach is majorization.