ON BOOK-COMPLETE GRAPH RAMSEY NUMBERS

It is shown that a graph of order N and average degree (d) over bar th at does not contain the book B-m = K-1 + K-1,K-m as a subgraph has ind ependence number at least Nf((d) over bar), where f(x) similar to (log x/x) (x --> infinity). From this result we find that the book-complet e graph Ramsey number satisfies r(B-m, K-n) less than or equal to mn(2 )/log(n/e). It is also shown that for every tree T-m with in edges, r( K-1 + T-m, K-n) less than or equal to (2m - 1)n(2)/log(n/e). (C) 1996 Academic Press, Inc.