Degree powers in C₅-free graphs

Abstract: Let

G

be a graph with degree sequence

d_{1}, d_{2}, l d o t s, d_{n}

. Given a positive integer

p

, denote by

e_{p} (G) = s u m_{i = 1}^{n} d_{i}^{p}

. Caro and Yuster introduced a Tur'an-type problem for

e_{p} (G)

: given an integer

p

, how large can

e_{p} (G)

be if

G

has no subgraph of a particular type. They got some results for the subgraph of particular type to be a clique of order

r + 1

and a cycle of even length, respectively. Denote by

e x_{p} (n, H)

the maximum value of

e_{p} (G)

taken over all graphs with

n

vertices that do not contain

H

as a subgraph. Clearly,

e x_{1} (n, H) = 2 e x (n, H)

, where

e x (n, H)

denotes the classical Tur'an number. In this paper, we consider

e x_{p} (n, C_{5})

and prove that for any positive integer

p

and sufficiently large

n

, there exists a constant

c = c (p)

such that the following holds: if

e x_{p} (n, C_{5}) = e_{p} (G)

for some

C_{5}

-free graph

G

of order

n

, then

G

is a complete bipartite graph having one vertex class of size

c n + o (n)

and the other

(1 - c) n + o (n)

.

Recommendations

Cites Work

Cited In (16)

This page was built for publication: Degree powers in \(C_5\)-free graphs