2025/11/17 by Zhou, Xiaoteng, Kazuya Haraguchi, Haraguchi, Kazuya +2
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2511.12943
Given a family of graphs F, a graph G is F-saturated if it is F-free but the addition of any missing edge creates a copy of some F ∈ F. The study of the minimum number of edges in F-saturated graphs is a central topic in extremal graph theory. Let (p+1)K2 denote a matching of size p+1. Determining the minimum number of edges in a (p+1)K2-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)K2-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 sat(n,(p+1)K2) 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.