Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph

Abstract

A graph $G$ is $F$-saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$. We prove that for $s\ge 3$ and $t\ge 2$, the minimum number of copies of $K_{1,t}$ in a $K_s$-saturated graph is $\Theta (n^{t/2})$. More precise results are obtained when $t=2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s\ge 4$ and $t\ge 3$, the minimum number of copies of $K_{2,t}$ in an $n$-vertex $K_s$-saturated graph is at least $\Omega (n^{t/5+8/5})$ and at most $O(n^{t/2+3/2})$. These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$-saturated graph are also obtained, but finding an asymptotic formula remains open.

References in corpus (1)

• $K_{r+1}$-saturated graphs with small spectral radius