Degree-restricted semi-saturation numbers of cliques and its applications

Abstract

A graph $G$ is said to be $F$-semi-saturated if the addition of any nonedge $e\notin E(G)$ would create a new copy of $F$ in $G+e$. The semi-saturation number $ssat(n,F)$ is the minimum number of edges in an $F$-semi-saturated graph of order $n$. In this paper we investigate the semi-saturation number of $K_r$ on $n$ vertices with maximal degree at most $\hat{I}”$, denoted by $ssa{t}^{\hat{I}}”(n,K_r)$. This investigation was suggested by Erd\H os, Rényi and Sós, who in 1966 considered the graph of diameter 2 with degree restrictions, equivalently $ssa{t}^{\hat{I}}”(n,K_3)$. The following are some of our results. For arbitrary $r\ge 4$, we show that the limit ${\lim }_{n\to \infty }ssa{t}^{cn}(n,K_r)/n$ exists for all $0<c\le 1$, except for some sparse values of $c$ contained in a countable and rational sequence $c_i\to 0$. Moreover, we establish the asymptotic behaviour of this limit for $\frac{r}{r+2}<c<1$ and determine the exact value of $ssa{t}^{\hat{I}}”(n,K_r)$ for some specific $\hat{I}”$. As an application, we determine the relation between the saturation number of the join graph $K_r\vee F$ and that of $F$ for a large class of pairs $(r,F)$.

26pages, 1 figure, 1 table