Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2509.17039 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908549978783744 |
|---|---|
| author | Yang, Gang Yang, Zixuan Zhang, Shenggui |
| author_facet | Yang, Gang Yang, Zixuan Zhang, Shenggui |
| contents | A graph $G$ is $F$-saturated if $G$ is $F$-free but for any edge $e$ in the complement of $G$ the graph $G + e$ contains $F$. Gerbner et al. (Discrete Math., 345 (2022), 112921) initiated the study of $rsat(n,F)$, the minimum number of edges in a regular $n$-vertex $F$-saturated graph, and they posed the problem of for which graphs $rsat(n, F )$ exists. Regarding this problem, we obtain the precise value of $rsat(n,(m+1)K_2)$ for all possible cases, where $(m+1)K_2$ denotes a matching of size $m+1$. As a natural counterpart, we also determine the maximum number of edges in a regular $n$-vertex $(m+1)K_2$-free graph for all $m\ge 1$ and $n\ge 2m+2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17039 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On saturation problems for matchings with regularity constraints Yang, Gang Yang, Zixuan Zhang, Shenggui Combinatorics A graph $G$ is $F$-saturated if $G$ is $F$-free but for any edge $e$ in the complement of $G$ the graph $G + e$ contains $F$. Gerbner et al. (Discrete Math., 345 (2022), 112921) initiated the study of $rsat(n,F)$, the minimum number of edges in a regular $n$-vertex $F$-saturated graph, and they posed the problem of for which graphs $rsat(n, F )$ exists. Regarding this problem, we obtain the precise value of $rsat(n,(m+1)K_2)$ for all possible cases, where $(m+1)K_2$ denotes a matching of size $m+1$. As a natural counterpart, we also determine the maximum number of edges in a regular $n$-vertex $(m+1)K_2$-free graph for all $m\ge 1$ and $n\ge 2m+2$. |
| title | On saturation problems for matchings with regularity constraints |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.17039 |