ON K-SATURATED GRAPHS WITH RESTRICTIONS ON THE DEGREES

A graph G is called k-saturated, where k greater than or equal to 3 is an integer, if G is K-k-free but the addition of any edge produces a K-k (we denote by K-k a complete graph on k: vertices). We investigate k-saturated graphs, and in particular the function F-k(n, D) defined as the minimal number of edges in a k-saturated graph on n vertices ha ving maximal degree at most D. This investigation was suggested by Haj nal, and the case k = 3 was studied by Furedi and Seress. The followin g are some of our results. For k = 4, we prove that F-4(n, D) = 4n - 1 5 for n > n(0) and [(2n - 1)/3] less than or equal to D less than or e qual to n - 2. For arbitrary k, we show that the limit lim(n --> infin ity) F-k(n, cn)/n exists for all 0 < c less than or equal to 1, except maybe for some values of c contained in a sequence c(i) --> 0. We als o determine the asymptotic behavior of this limit for c --> 0. We cons truct, for all k and all sufficiently large n, a k-saturated graph on n vertices with maximal degree at most 2k root n, significantly improv ing an upper bound due to Hanson and Seyffarth. (C) 1996 John Wiley & Sons, Inc.