Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 331.05122
Autor: Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title: The size Ramsey number. (In English)
Source: Period. Math. Hung. 9, 145-161 (1978).
Review: Let C be the class of all graphs G which satisfy G ––> (G1,G2). As a way of measuring minimality for members of C, we define the size Ramsey number \hat r(G1,G2) by \hat r(G1,G2) = maxG in C |E(G)|. As usual, \hat r(G) signifies \hat r(G,G). For comparison purposes, we let \hat R(G1,G2): = \binom{r(G1,G2)}{2}, where r(G1,G2) denotes the standard Ramsey number. It is clear that \hat r(G1,G2) \leq \hat R(G1,G2) and we note in the paper that for all m,n, \hat r(Km,Kn) = \hat R(Km,Kn). On the other hand, \hat r can be much less than \hat R, a notion made precise by the following definition. An infinite sequence of graphs {Gn} is said to be an o-sequence if \hat r(Gn) = o(\hat R(G)n)) (n ––> oo). We prove several theorems related to the o-sequence concept. For example, we prove that if m is fixed, then {Km,n} is an o-sequence. In the course of this work, we find some new results for standard Ramsey numbers. For example, letting Km * \bar Kn denote the graph obtained from Km by making one of its vertices adjacent to n additional vertices, we prove that if m is fixed and n is sufficiently large, then r(Km * \bar Kn) = (m-1)(m+n-1)+1.
Reviewer: P.Erdös
Classif.: * 05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag