On degree powers in the degenerate Turán problem

Abstract

Given a graph $G$ with degree sequence $d_1,\dots ,d_n$ and a positive real number $p$, let $e_p(G)={\sum }_{i=1}^n{d}_i^p$. For a fixed family of graphs $\mathcal{F}$, let $e{x}_p(n,\mathcal{F})$ denote the maximum value of $e_p(G)$ over all $\mathcal{F}$-free graphs $G$ on $n$ vertices. In 2000, Caro and Yuster introduced the following Turán-type problem: For a positive integer $p$ and a fixed graph $F$, determine $e{x}_p(n,F)$, and characterize the extremal graphs $G$ on $n$ vertices that attain $e{x}_p(n,F)$. Recently, Gao, Liu, Ma and Pikhurko proved that $e{x}_p(n,\mathcal{F})=(\tau (\mathcal{F})-1+o(1))n^p$ for real $p>\frac{1}{1-\alpha }$, where $\mathcal{F}$ is a degenerate family of graphs with classical Turán number $ex(n,\mathcal{F})=O(n^{1+\alpha })$ for some $\alpha \in [0,1)$, and $\tau (\mathcal{F})$ is the minimum size of an independent vertex cover over all bipartite graphs $F\in \mathcal{F}$. Based on their method, we obtain a stability result for $e{x}_p(n,\mathcal{F})$, and prove that all extremal graphs must contain the complete bipartite graph $K_{\tau (\mathcal{F})-1,n-\tau (\mathcal{F})+1}$ when $n$ is sufficiently large. Our results can be used to deduce all previously known results about $e{x}_p(n,F)$ when $F$ is a bipartite graph and $n$ is sufficiently large. We also obtain several new exact results for $e{x}_p(n,F)$, namely, when $F$ is an even cycle, a complete bipartite graph, a discrete hypercube, a caterpillar forest, and a spider forest.

22 pages, 1 figure