This analysis finds exact edge counts in regular F-saturated graphs, indicating bounds for various matchings.
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₂) for all possible cases, where (m+1)K₂ 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₂-free graph for all m≥ 1 and n≥ 2m+2.
No takes yet. Share an insight, caveat, or question.
Yang et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: