Turán's problem and Ramsey numbers for trees

Abstract: Let

T_{n}^{1} = (V, E_{1})

and

T_{n}^{2} = (V, E_{2})

be the trees on

n

vertices with

V = v_{0}, v_{1}, l d o t s, v_{n - 1}

,

E_{1} = v_{0} v_{1}, l d o t s, v_{0} v_{n - 3}, v_{n - 4} v_{n - 2}, v_{n - 3} v_{n - 1}

, and

. In this paper, for

p g e n g e 5

we obtain explicit formulas for

e x (p; T_{n}^{1})

and

e x (p; T_{n}^{2})

, where

e x (p; L)

denotes the maximal number of edges in a graph of order

p

not containing

L

as a subgraph. Let

r (G s b 1, G s b 2)

be the Ramsey number of the two graphs

G_{1}

and

G_{2}

. In this paper we also obtain some explicit formulas for

r (T_{m}, T_{n}^{i})

, where

i i n 1, 2

and

T_{m}

is a tree on

m

vertices with

D e l t a (T_{m}) l e m - 3

.

Recommendations

Cited in

(10)

This page was built for publication: Turán's problem and Ramsey numbers for trees