\(K_r\)-saturated graphs and the two families theorem

Asier Calbet¹

¹Queen Mary University of London

The electronic journal of combinatorics, Tome 31 (2024) no. 4

Résumé

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 \geq 3$ and $t \geq 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} \ll_r c(r,t) \leq 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)=\Theta_r \left(4^t t^{-1/2} \right)$. Moreover, we investigate the dependence on $r$, obtaining the estimates$$ \frac{4^{t-r}}{\sqrt{t-r+3}} + r^2 \ll c(r,t) \ll \frac{4^{t-r} \min{(r,\sqrt{t-r+3})}}{\sqrt{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 / \log e)$, uniformly in $r \geq 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.

Détail

DOI : 10.37236/12718

Classification : 05C35, 05D05, 05C75
Mots-clés : maximal graph, \((a, b, c)\)-variable modified set system