The saturation number for unions of four cliques
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910571969904640 |
|---|---|
| author | Li, Ruo-Xuan Hao, Rong-Xia He, Zhen Zhu, Wen-Han |
| author_facet | Li, Ruo-Xuan Hao, Rong-Xia He, Zhen Zhu, Wen-Han |
| contents | A graph $G$ is $H$-saturated if $H$ is not a subgraph of $G$ but $H$ is a subgraph of $G + e$ for any edge $e$ in $\overline{G}$. The saturation number $sat(n,H)$ for a graph $H$ is the minimal number of edges in any $H$-saturated graph of order $n$. The $sat(n, K_{p_1} \cup K_{p_2} \cup K_{p_3})$ with $p_3 \ge p_1 + p_2$ was given in [Discrete Math. 347 (2024) 113868]. In this paper, $sat(n,K_{p_1} \cup K_{p_2} \cup K_{p_3} \cup K_{p_4})$ with $p_{i+1} - p_i \ge p_1$ for $2 \le i\le 3$ and $4\le p_1\le p_2$ is determined. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_11644 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The saturation number for unions of four cliques Li, Ruo-Xuan Hao, Rong-Xia He, Zhen Zhu, Wen-Han Combinatorics 05C35 A graph $G$ is $H$-saturated if $H$ is not a subgraph of $G$ but $H$ is a subgraph of $G + e$ for any edge $e$ in $\overline{G}$. The saturation number $sat(n,H)$ for a graph $H$ is the minimal number of edges in any $H$-saturated graph of order $n$. The $sat(n, K_{p_1} \cup K_{p_2} \cup K_{p_3})$ with $p_3 \ge p_1 + p_2$ was given in [Discrete Math. 347 (2024) 113868]. In this paper, $sat(n,K_{p_1} \cup K_{p_2} \cup K_{p_3} \cup K_{p_4})$ with $p_{i+1} - p_i \ge p_1$ for $2 \le i\le 3$ and $4\le p_1\le p_2$ is determined. |
| title | The saturation number for unions of four cliques |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2408.11644 |