On a Question of Erdös and Faudree on the Size Ramsey Numbers

Publication date 5 September 2018

Abstract: For given simple graphs

G_{1}

and

G_{2}

, the size Ramsey number

h a t R (G_{1}, G_{2})

is the smallest positive integer

m

, where there exists a graph

G

with

m

edges such that in any edge coloring of

G

with two colors red and blue, there is either a red copy of

G_{1}

or a blue copy of

G_{2}

. In 1981, ErdH{o}s and Faudree investigated the size Ramsey number

h a t R (K_{n}, t K_{2})

, where

K_{n}

is a complete graph on

n

vertices and

t K_{2}

is a matching of size

t

. They obtained the value of

h a t R (K_{n}, t K_{2})

when

n g e q 4 t - 1

as well as for

t = 2

and asked for the behavior of these numbers when

t

is much larger than

n

. In this regard, they posed the following interesting question: For every positive integer

n

, is it true that

lim_{t o infty} frac{hat{R}(K_n,tK_2)} {t, hat{R}(K_n,K_2)} = minleft{dfrac{�inom{n+2t-2}{2}} {t�inom{n}{2}}mid tin mathbb{N} ight} ?

In this paper, we obtain the exact value of

h a t R (K_{n}, t K_{2})

for every positive integers

n, t

and as a byproduct, we give an affirmative answer to the question of ErdH{o}s and Faudree.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: On a Question of Erdös and Faudree on the Size Ramsey Numbers