The weak saturation number of $\boldsymbol{K_{2, t}}$
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910295571562496 |
|---|---|
| author | Miralaei, Meysam Mohammadian, Ali Tayfeh-Rezaie, Behruz |
| author_facet | Miralaei, Meysam Mohammadian, Ali Tayfeh-Rezaie, Behruz |
| contents | For two graphs $G$ and $F$, we say that $G$ is weakly $F$-saturated if $G$ contains no copy of $F$ as a subgraph and one could join all the nonadjacent pairs of vertices of $G$ in some order so that a new copy of $F$ is created at each step. The weak saturation number $\mathrm{wsat}(n, F)$ is the minimum number of edges of a weakly $F$-saturated graph on $n$ vertices. In this paper, we examine $\mathrm{wsat}(n, K_{s, t})$, where $K_{s, t}$ is the complete bipartite graph with parts of sizes $s$ and $ t $.
We determine $\mathrm{wsat}(n, K_{2, t})$, correcting a previous report in the literature. It is also shown that $\mathrm{wsat}(s+t, K_{s,t})=\binom{s+t-1}{2}$ if $\gcd(s, t)=1$ and $\mathrm{wsat}(s+t, K_{s,t})=\binom{s+t-1}{2}+1$, otherwise. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_10939 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The weak saturation number of $\boldsymbol{K_{2, t}}$ Miralaei, Meysam Mohammadian, Ali Tayfeh-Rezaie, Behruz Combinatorics 05C35 For two graphs $G$ and $F$, we say that $G$ is weakly $F$-saturated if $G$ contains no copy of $F$ as a subgraph and one could join all the nonadjacent pairs of vertices of $G$ in some order so that a new copy of $F$ is created at each step. The weak saturation number $\mathrm{wsat}(n, F)$ is the minimum number of edges of a weakly $F$-saturated graph on $n$ vertices. In this paper, we examine $\mathrm{wsat}(n, K_{s, t})$, where $K_{s, t}$ is the complete bipartite graph with parts of sizes $s$ and $ t $. We determine $\mathrm{wsat}(n, K_{2, t})$, correcting a previous report in the literature. It is also shown that $\mathrm{wsat}(s+t, K_{s,t})=\binom{s+t-1}{2}$ if $\gcd(s, t)=1$ and $\mathrm{wsat}(s+t, K_{s,t})=\binom{s+t-1}{2}+1$, otherwise. |
| title | The weak saturation number of $\boldsymbol{K_{2, t}}$ |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2211.10939 |