Partite saturation number of cycles

Abstract

A graph $H$ is said to be $F$-saturated relative to $G$, if $H$ does not contain any copy of $F$, but the addition of any edge $e$ in $E(G)\backslash E(H)$ would create a copy of $F$. The minimum size of an $F$-saturated graph relative to $G$ is denoted by $sat(G,F)$. Let $K_k^n$ be the complete $k$-partite graph containing $n$ vertices in each part and $C_{\ell }$ be the cycle of length $\ell$. In this paper we give an asymptotically tight bound of $sat(K_k^n,C_{\ell })$ for all $\ell \ge 4,k\ge 2$ except $(\ell ,k)=(4,4)$. Moreover, we determined the exact value of $sat(K_k^n,C_{\ell })$ for $k>\ell =4$ and $5\ge \ell >k\ge 3$ and $(\ell ,k)=(6,2)$.

31 pages, 21 figures, 9 theorems