Name
Abstract | ||
|---|---|---|
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) dened 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 Furedi 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!1Fk(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 behaviour of this limit for c! 0. We construct, for all k and all suciently large |
Year | DOI | Venue |
|---|---|---|
1996 | 3.3.CO;2-3" target="_self" class="small-link-text"10.1002/(SICI)1097-0118(199609)23:13.3.CO;2-3 | Journal of Graph Theory |
Keywords | Field | DocType |
k-saturated graph,complete graph | Random regular graph,Complete graph,Discrete mathematics,Combinatorics,Bound graph,Vertex (geometry),Rank (graph theory),Degree (graph theory),Distance-regular graph,Mathematics,Path graph | Journal |
Volume | Issue | Citations |
23 | 1 | 1 |
PageRank | References | Authors |
0.37 | 1 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Paul Erdős | 2 | 264 | 42.20 |
| Ron Holzman | 3 | 287 | 43.78 |
| michael krivelevich | 4 | 1688 | 179.90 |