Minimum saturated graphs for unions of 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_ | 1866929319298727936 |
|---|---|
| author | Zhu, Wen-Han Hao, Rong-Xia He, Zhen |
| author_facet | Zhu, Wen-Han Hao, Rong-Xia He, Zhen |
| contents | Let $H$ be a fixed graph. A graph $G$ is called {\it $H$-saturated} if $H$ is not a subgraph of $G$ but the addition of any missing edge to $G$ results in an $H$-subgraph. The {\it saturation number} of $H$, denoted $sat(n,H)$, is the minimum number of edges over all $H$-saturated graphs of order $n$, and $Sat(n,H)$ denote the family of $H$-saturated graphs with $sat(n,H)$ edges and $n$ vertices. In this paper, we resolve a conjecture of Chen and Yuan in[Discrete Math. 347(2024)113868] by determining $Sat(n,K_p\cup (t-1)K_q)$ for every $2\le p\le q$ and $t\ge 2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12204 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimum saturated graphs for unions of cliques Zhu, Wen-Han Hao, Rong-Xia He, Zhen Combinatorics 05C35 Let $H$ be a fixed graph. A graph $G$ is called {\it $H$-saturated} if $H$ is not a subgraph of $G$ but the addition of any missing edge to $G$ results in an $H$-subgraph. The {\it saturation number} of $H$, denoted $sat(n,H)$, is the minimum number of edges over all $H$-saturated graphs of order $n$, and $Sat(n,H)$ denote the family of $H$-saturated graphs with $sat(n,H)$ edges and $n$ vertices. In this paper, we resolve a conjecture of Chen and Yuan in[Discrete Math. 347(2024)113868] by determining $Sat(n,K_p\cup (t-1)K_q)$ for every $2\le p\le q$ and $t\ge 2$. |
| title | Minimum saturated graphs for unions of cliques |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2404.12204 |