## 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 Kk-free, but the addition of any edge produces a Kk (where Kk 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 Fk(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 F4(n,D) = 4n-15 for n > n0 and \lfloor(2n-1)/3\rfloor \leq D \leq n-2. Also, it is shown that limn ––> oo Fk(n,cn) exists for all 0 < c \leq 1, except maybe for some values of c contained in a sequence ci ––> 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