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