A note on the minimum size of matching-saturated graphs☆

作者：Zhang, Xuechun; Lu, Hongliang; Yu, Qinglin^*

来源：Discrete Applied Mathematics, 2024, 348: 1-5.

DOI：10.1016/j.dam.2024.01.017

• Saturated graph
• Matching
• Fractional matching

Let s, m, n be positive integers and F be a graph. A graph G is called F-saturated if F is not a subgraph of G but G + e contain a copy of F for every edge e is an element of E(G), where G is the complement graph of G. Let sat(n, F) be the minimum number of edges over all F-saturated graphs with order n and Sat(n, F) denotes the family of F-saturated graphs with sat(n, F) edges and n vertices. Let mK(2) denote a matching of size m and let sK2f sat(n,mK(2)), and characterize Sat(n,mK2) when root n + 2m < n < 3m. Moreover, we also denote a fractional matching of size s. In this paper, we determine the exact value of determine the exact value of sat(n, sK(2)(f )), and characterize Sat(n, sK(2)(f)) when n > 2s. The main results provide partial answers to the open question posed by Faudree et al. (2011).

• 单位
  西安交通大学