##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 857.05051

**Autor: ** Alon, Noga; Erdös, Paul; Holzman, Ron; Krivelevich, Michael

**Title: ** On k-saturated graphs with restrictions on the degrees. (In English)

**Source: ** J. Graph Theory 23, No.1, 1-20 (1996).

**Review: ** A graph G is called k-saturated if it is K_{k}-free, but the addition of any edge produces a K_{k} (where K_{k} is the complete graph of order k). There is an old result that if G has order n and is k-saturated, then the number of edges in G is at least (k-2)n-\binom{k-1}{2}. However, the extremal examples contain each vertex of degree n-1. This paper defines F_{k}(n,D) to be the minimal number of edges in a k-saturated graph of order n and maximum degree at most D. The case k = 3 has been studied by *Z. Füredi* and *Á. Seress* [J. Graph Theory 18, No. 1, 11-24 (1994; Zbl 787.05054)].

In this paper it is shown that F_{4}(n,D) = 4n-15 for n > n_{0} and \lfloor(2n-1)/3\rfloor \leq D \leq n-2. Also, it is shown that **lim**_{n ––> oo} F_{k}(n,cn) exists for all 0 < c \leq 1, except maybe for some values of c contained in a sequence c_{i} ––> 0. For sufficiently large n, they also construct some k-saturated graphs of order n with maximal degree at most 2k\sqrt n, significantly improving earlier results.

**Reviewer: ** C.Jagger (Cambridge)

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C65 Hypergraphs

**Keywords: ** maximum degree; k-saturated graphs

**Citations: ** Zbl 787.05054

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag