TY - JOUR
T1 - On k-Saturated Graphs with Restrictions on the Degrees
AU - Alon, Noga
AU - Erdos, Paul
AU - Holzman, Ron
AU - Krivelevich, Michael
PY - 1996/9
Y1 - 1996/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=1842429967&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1842429967&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1097-0118(199609)23:1<1::AID-JGT1>3.0.CO;2-O
DO - 10.1002/(SICI)1097-0118(199609)23:1<1::AID-JGT1>3.0.CO;2-O
M3 - Article
AN - SCOPUS:1842429967
VL - 23
SP - 1
EP - 20
JO - Journal of Graph Theory
JF - Journal of Graph Theory
SN - 0364-9024
IS - 1
ER -