On k-Saturated Graphs with Restrictions on the Degrees

Noga Alon, Paul Erdos, Ron Holzman, Michael Krivelevich

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


A graph G is called k-saturated, where k ≥ 3 is an integer, if G is Kk-free but the addition of any edge produces a Kk (we denote by Kk a complete graph on k vertices). We investigate k-saturated graphs, and in particular the function Fk(n, D) defined as the minimal number of edges in a k-saturated graph on n vertices having maximal degree at most D. This investigation was suggested by Hajnal, and the case k = 3 was studied by Füredi and Seress. The following are some of our results. For k = 4, we prove that F4(n, D) = 4n - 15 for n > n0 and [(2n - 1)/3] ≤ D ≤ n - 2. For arbitrary k, we show that the limit limn→∞ Fk(n, cn)/n exists for all 0 < c ≤ 1, except maybe for some values of c contained in a sequence ci → 0. We also determine the asymptotic behavior of this limit for c → 0. We construct, for all k and all sufficiently large n, a k-saturated graph on n vertices with maximal degree at most 2k√n, significantly improving an upper bound due to Hanson and Seyffarth.

Original languageEnglish (US)
Pages (from-to)1-20
Number of pages20
JournalJournal of Graph Theory
Issue number1
StatePublished - Sep 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Geometry and Topology


Dive into the research topics of 'On k-Saturated Graphs with Restrictions on the Degrees'. Together they form a unique fingerprint.

Cite this