Saturation numbers of K₂\vee P_k

2025/11/25 by Zhang, Xiaoxue, You, Lihua, Zhao, Xinghui
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2511.20213

Abstract

A graph G is called H-saturated if G contains no copy of H, but G+e contains a copy of H for any edge e∈ E(G). The saturation number of H is the minimum number of edges in an H-saturated graph of order n, denoted by sat(n,H). In this paper, we investigate sat(n,K₂\vee P_k), where k≥ 3. Let a_k be an integer, defined as follows: a_k=k for 3≤ k≤ 5; a_k=3⋅ 2^t-1-2 for k=2t≥ 6; and a_k=2^t+1-2 for k=2t+1≥ 7. We show that sat(n, K₂\vee P_k)=2n-3+sat(n-2,P_k) for n≥ a_k+2 and k≥ 3, characterize the K₂\vee P_k-saturated graphs with sat(n,K₂\vee P_k) edges, the K₁\vee P_k-saturated graphs with sat(n,K₁\vee P_k) edges for 3≤ k≤5 and the P_k-saturated graphs with sat(n, P_k) edges for 3≤ k≤4. Furthermore, we propose some questions for further research.

Citations

• The saturation number of W 4
• The saturation number of wheels
• Minimum saturated graphs for unions of cliques
• Some results on the saturation number for unions of cliques
• The saturation number of C₆
• A lower bound on the saturation number, and graphs for which it is sharp
• The saturation number of K_3,3
• Cycle-saturated graphs with minimum number of edges

Related

• The saturation number for unions of four cliques
• Few T copies in H-saturated graphs
• Cycle-saturated graphs with minimum number of edges
• The saturation number of C₆
• Saturation Numbers for Linear Forests P₆ + tP₂