Partite saturation number of cycles

2024/10/15 by Xu, Yiduo, He, Zhen, Lu, Mei
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2410.11194

Abstract

A graph H is said to be F-saturated relative to G, if H does not contain any copy of F, but the addition of any edge e in E(G)\backslash E(H) would create a copy of F. The minimum size of an F-saturated graph relative to G is denoted by sat(G,F). Let K_kⁿ be the complete k-partite graph containing n vertices in each part and C_ℓ be the cycle of length ℓ. In this paper we give an asymptotically tight bound of sat(K_kⁿ,C_ℓ) for all ℓ ≥ 4, k ≥ 2 except (ℓ,k)=(4,4). Moreover, we determined the exact value of sat(K_kⁿ,C_ℓ) for k>ℓ=4 and 5 ≥ ℓ>k ≥ 3 and (ℓ,k)=(6,2).

Related

• Minimizing the number of edges in C_{≥ r}-saturated graphs
• Minimum saturated graphs without 4-cycles and 5-cycles
• Cycle-saturated graphs with minimum number of edges
• The saturation number of W 4
• On saturation numbers of complete multipartite graphs and even cycles