Premium
On k ‐saturated graphs with restrictions on the degrees
Author(s) -
Alon Noga,
Erdös Paul,
Holzman Ron,
Krivelevich Michael
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199609)23:1<1::aid-jgt1>3.0.co;2-o
Subject(s) - combinatorics , mathematics , graph , upper and lower bounds , degree (music) , limit (mathematics) , discrete mathematics , physics , mathematical analysis , acoustics
A graph G is called k ‐saturated, where k ≥ 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 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 F 4 ( n,D ) = 4 n − 15 for n > n 0 and [(2 n − 1)/3] ≤ D ≤ n − 2. For arbitrary k, we show that the limit lim n→∞ F k ( n,cn )/ n exists for all 0 > c ≤ 1, except maybe for some values of c contained in a sequence c i → 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 2 k √ n , significantly improving an upper bound due to Hanson and Seyffarth. © 1996 John Wiley & Sons, Inc.