ON A PROBLEM OF ERDŐS ABOUT GRAPHS WHOSE SIZE IS THE TURÁN NUMBER PLUS ONE

Abstract: We consider finite simple graphs. Given a graph

H

and a positive integer

n,

the Tur'{a}n number of

H

for the order

n,

denoted

m e x (n, H),

is the maximum size of a graph of order

n

not containing

H

as a subgraph. ErdH{o}s posed the following problem in 1990: "For which graphs

H

is it true that every graph on

n

vertices and

m e x (n, H) + 1

edges contains at least two

H

s? Perhaps this is always true." We solve the second part of this problem in the negative by proving that for every integer

k g e 4,

there exists a graph

H

of order

k

and at least two orders

n

such that there exists a graph of order

n

and size

m e x (n, H) + 1

which contains exactly one copy of

H .

Denote by

C_{4}

the

4

-cycle. We also prove that for every integer

n

with

6 l e n l e 11,

there exists a graph of order

n

and size

m e x (n, C_{4}) + 1

which contains exactly one copy of

C_{4},

but for

n = 12

or

n = 13,

the minimum number of copies of

C_{4}

in a graph of order

n

and size

m e x (n, C_{4}) + 1

is

2.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: ON A PROBLEM OF ERDŐS ABOUT GRAPHS WHOSE SIZE IS THE TURÁN NUMBER PLUS ONE