A Turán Type Problem Concerning the Powers of the Degrees of a Graph (revised)

2004/01/28 by Y. Caro, R. Yuster · 2 citations
Mathematics · #math.CO #msc:05C35 #msc:05C07

paper · pdf

published as The Electronic Journal of Combinatorics 7 (2000), #R47 · 14 Pages

arxiv created 2004/01/28 · arxiv updated 2009/12/01

Abstract

For a graph G whose degree sequence is d₁,..., d_n, and for a positive integer p, let e_p(G)=∑_i=1ⁿ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₁(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.

Cited by

• Exact Turán number of the Fano plane in the ℓ₂-norm
• Turán density of tight cycles minus one edge in the ℓ₂-norm

Related

• A Turán-type problem on degree sequence
• Degree powers in C₅-free graphs
• Degree powers in graphs with a forbidden forest
• On degree power sum in P_k-free graphs
• Nondegenerate Turán problems under (t,p)-norms