Partite saturation number of cycles
| Autor: | Xu, Yiduo, He, Zhen, Lu, Mei |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 \geq 4, k \geq 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 \geq \ell>k \geq 3$ and $(\ell,k)=(6,2)$. Comment: 31 pages, 21 figures, 9 theorems |
| Databáze: | arXiv |
| Externí odkaz: |
|