The Minimum Number of Edges in $(p+1)K_2$-Saturated Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917084939681792 |
|---|---|
| author | Zhou, Xiaoteng Haraguchi, Kazuya Yuan, Hanchun |
| author_facet | Zhou, Xiaoteng Haraguchi, Kazuya Yuan, Hanchun |
| contents | Given a family of graphs $\mathcal{F}$, a graph $G$ is $\mathcal{F}$-saturated if it is $\mathcal{F}$-free but the addition of any missing edge creates a copy of some $F \in \mathcal{F}$. The study of the minimum number of edges in $\mathcal{F}$-saturated graphs is a central topic in extremal graph theory.
Let $(p+1)K_2$ denote a matching of size $p+1$. Determining the minimum number of edges in a $(p+1)K_{2}$-saturated graph is a fundamental question in this area, explicitly posed as Problem 9 in the survey by Faudree et al. (2011). In this paper, we refine the structural analysis of $(p+1)K_2$-saturated graphs and derive an explicit formula for the number of edges in terms of a single integer parameter. By minimizing this formula we determine $\mathrm{sat}(n,(p+1)K_2)$ for all $n>2p$, thereby resolving Problem 9 in full generality and extending earlier results of Kászonyi--Tuza (1986) and Zhang--Lu--Yu (2024). Moreover, by maximizing the same formula we recover the classical Erdős--Gallai (1959) upper bound on the number of edges in such graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12943 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Minimum Number of Edges in $(p+1)K_2$-Saturated Graphs Zhou, Xiaoteng Haraguchi, Kazuya Yuan, Hanchun Combinatorics 05C35, 05C70 Given a family of graphs $\mathcal{F}$, a graph $G$ is $\mathcal{F}$-saturated if it is $\mathcal{F}$-free but the addition of any missing edge creates a copy of some $F \in \mathcal{F}$. The study of the minimum number of edges in $\mathcal{F}$-saturated graphs is a central topic in extremal graph theory. Let $(p+1)K_2$ denote a matching of size $p+1$. Determining the minimum number of edges in a $(p+1)K_{2}$-saturated graph is a fundamental question in this area, explicitly posed as Problem 9 in the survey by Faudree et al. (2011). In this paper, we refine the structural analysis of $(p+1)K_2$-saturated graphs and derive an explicit formula for the number of edges in terms of a single integer parameter. By minimizing this formula we determine $\mathrm{sat}(n,(p+1)K_2)$ for all $n>2p$, thereby resolving Problem 9 in full generality and extending earlier results of Kászonyi--Tuza (1986) and Zhang--Lu--Yu (2024). Moreover, by maximizing the same formula we recover the classical Erdős--Gallai (1959) upper bound on the number of edges in such graphs. |
| title | The Minimum Number of Edges in $(p+1)K_2$-Saturated Graphs |
| topic | Combinatorics 05C35, 05C70 |
| url | https://arxiv.org/abs/2511.12943 |