K_r-Saturated Graphs and the Two Families Theorem
We say that a graph G is K_r-saturated if G contains no copy of K_r but adding any new edge to G creates a copy of K_r. Let sat(n,K_r,t) be the minimum number of edges in a K_r-saturated graph on n vertices with minimum degree at least t. Day showed that for fixed r ≥ 3 and t ≥ r-2, sat(n,K_r,t)=tn-c(r,t) for large enough n, where c(r,t) is a constant depending on r and t, and proved the bounds 2^t t^3/2 _r c(r,t) ≤ t^t^2t^2 for fixed r and large t. In this paper we show that for fixed r and large t, the order of magnitude of c(r,t) is given by c(r,t)=Θ_r (4^t t^-1/2 ). Moreover, we investigate the dependence on r, obtaining the estimates 4^t-r t-r+3 + r^2 c(r,t) 4^t-r (r,t-r+3) t-r+3 + r^2 . We further show that for all r and t, there is a finite collection of graphs such that all extremal graphs are blow-ups of graphs in the collection. Using similar ideas, we show that every large K_r-saturated graph with e edges has a vertex cover of size O(e / e), uniformly in r ≥ 3. This strengthens a previous result of Pikhurko. We also provide examples for which this bound is tight. A key ingredient in the proofs is a new version of Bollobás’s Two Families Theorem. , number=4, journal=The Electronic Journal of Combinatorics, author=Calbet, Asier, year=2024, month=Dec., pages=#P4.68