Minimizing the number of edges in (P_k ∪ K₃)-saturated connected graphs

¹ School of Mathematics, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, P.R. China
² MIIT Key Laboratory of Mathematical Modelling and High Performance Computing of Air Vehicles, Nanjing, Jiangsu 210016, P.R. China

^* Corresponding author: yuyingli1205@163.com

Received: 2 October 2022
Accepted: 12 February 2023

Abstract

For a graph H, a graph G is H-saturated if it contains no copy of H as a (not necessarily induced) subgraph, but the addition of any edge missing from G creates a copy of H in the resultant graph. The connected saturation number sat′(n, H) is defined as the minimum number of edges in H-saturated connected graphs on n vertices. In this paper we consider the (P_k ∪ K₃)-saturated connected graphs on n vertices and focus on the determination of sat′(n, P_k ∪ K₃). We prove that n + 2 ≤ sat′(n, P_k ∪ K₃) ≤ n + 3k-6/2 for n > 3k+4/2 with k ≥ 4 and characterize the extremal graphs at which the upper bounds are attained. Moreover, the exact values of sat′(n, P_k ∪ K₃) are determined with k ∈ {3, 4} and we get sat(n, P₂ ∪ K₃) = sat′(n, P₂ ∪ K₃) = n.