Minimizing the number of edges in C_{≥ r}-saturated graphs

2020/02/23 by Yue Ma, Ma, Yue, Xinmin Hou +5
Computer Science · Mathematics · #05C35 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2002.09882

openalex publication_date 2020/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a family of graphs F, a graph G is said to be F-saturated if G does not contain a copy of F as a subgraph for any F\inF but the addition of any edge e∉ E(G) creates at least one copy of some F\inF within G. The minimum size of an F-saturated graph on n vertices are called the saturation number, denoted by \sat(n, F). Let C_{≥ r} be the family of cycles of length at least r. Ferrara et al. (2012) gave lower and upper bounds of \sat(n, C_{≥ r}) and determined the exact values of \sat(n, C_{≥ r}) for 3≤ r≤ 5. In this paper, we determine the exact value of \sat(n,C_{≥ r}) for r=6 and 28≤ \fracn2≤ r≤ n and give new upper and lower bounds for the other cases.

Related

• Minimum saturated graphs without 4-cycles and 5-cycles
• Some results on minimum saturated graphs
• Cycle-saturated graphs with minimum number of edges
• Partite saturation number of cycles
• C_2k-saturated graphs with no short odd cycles