A Turán type problem concerning the powers of the degrees of a graph

Yair Caro ; Raphael Yuster

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

For a graph $G$ whose degree sequence is $d_{1},\ldots ,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.

Détail

DOI : 10.37236/1525

Classification : 05C35, 05C07
Mots-clés : degree sequence, Turán number