Maximizing the density of K_t's in graphs of bounded degree and clique number

Abstract: Zykov showed in 1949 that among graphs on

n

vertices with clique number

o m e g a (G) l e o m e g a

, the Tur'an graph

T_{o m e g a} (n)

maximizes not only the number of edges but also the number of copies of

K_{t}

for each size

t

. The problem of maximizing the number of copies of

K_{t}

has also been studied within other classes of graphs, such as those on

n

vertices with maximum degree

D e l t a (G) l e D e l t a

. We combine these restrictions and investigate which graphs with

D e l t a (G) l e D e l t a

and

o m e g a (G) l e o m e g a

maximize the number of copies of

K_{t}

per vertex. We define

f_{t} (D e l t a, o m e g a)

as the supremum of

h o_{t}

, the number of copies of

K_{t}

per vertex, among such graphs, and show for fixed

t

and

o m e g a

that

f_{t} (D e l t a, o m e g a) = (1 + o (1)) h o_{t} (T_{o m e g a} (D e l t a + l f l o o r f r a c D e l t a o m e g a - 1 f l o o r))

. For two infinite families of pairs

(D e l t a, o m e g a)

, we determine

f_{t} (D e l t a, o m e g a)

exactly for all

t g e 3

. For another we determine

f_{t} (D e l t a, o m e g a)

exactly for the two largest possible clique sizes. Finally, we demonstrate that not every pair

(D e l t a, o m e g a)

has an extremal graph that simultaneously maximizes the number of copies of

K_{t}

per vertex for every size

t

.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number