# Saturation Numbers for Linear Forests2P4∪tP2∗

Authors: Feifei Song; Yan Zou; Hengdi Su
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

For a given graphF, graph G is called F-saturated if G does not contain a copy of F, but G+e has a copy of F, where e∉EG. The saturation number, denoted by satn,F, is the minimum size of a graph with order n in all F-saturated graphs. For n≥6t+22, this paper considers the saturation number of linear forests 2P4∪tP2 and describes the extremal graph.


---

## Body

## 1. Introduction

In this article, we only deal with simple graph. Usually, the path and the complete graph withn vertices are denoted by Pn and Kn, respectively. For terminology and notations not undefined in this paper, the reader can refer to [1].For a given graphF, graph G is called F-saturated if G does not contain a copy of F, but G+e has a copy of F, where e∉EG. The famous Turán number [2], denoted by exn,F, is the maximum number size of graphs in all F-saturated graphs with size n. As a complement, saturation number, denoted by satn,F, is the minimum size of graphs in all F-saturated graphs with size n. We use SAT¯n,F which denotes the set of graphs with a minimum number size in SATn,F.In 1964, Erdős et al. introduced the notion of the saturation number and gave the saturation number ofKt in [3]. Kászonyi et al. gave the general upper bound of satn,F in [4], when F is a kind of forbidden graphs. Then, for a wider range of graphs F, saturation number of F has been studied by many scholars, for example, k-edge-connected graph [5], cliques [6, 7], complete bipartite graphs [8, 9], nearly complete graphs [10], books [11], cycles [12–17], trees [18, 19], and forests [20–22]. The reader can see summary of known results in [23].In [24], Bushaw et al. gave the Turán number for the linear forest. Corresponding to that, Chen et al. concentrated on the saturation numbers in [20]. They obtained an interesting set of results; some of those are shown as the following results.Theorem 1 (see [20]).
(i)
Letnbe positive integers such that sufficiently large; then,satn,P3∪tP2=3tand the extremal graph istK3∪n−3tK1(ii)
Letnandtbe positive integers such thatnis sufficiently large andt≥1; then,satn,P4∪tP2=3t+7and the extremal graph isK5∪t−1K3∪n−3t−2K1(iii)
Letnbe positive integers such that it is sufficiently large; then,satn,P5∪P2=15and the extremal graph isK6∪n−6K1
LetTp,q be obtained from K2 by attaching p disjoint triangles to one vertex of K2 and attaching q disjoint triangles to another vertex of K2 (see Figure 1).
In this paper, we prove the following theorem.Figure 1
The graphTp,q.Theorem 2.
Supposetandnare positive integers such thatn≥6t+12. Then,satn,2P4∪tP2=3t+10andSAT¯n,2P4∪tP2=Tp,q∪aK3∪n−2t−a−8K1:p≥2,q≥2andp+q+a=t+3forn≥6t+22.
In what follows, Section2 lists several useful results and study property of 2P4∪tP2-saturated graphs. In Section 3, we give the proof of Theorem 2.


## 2. Preliminaries

Firstly, we introduce some notations. For a graphG, the edge set and vertex set are denoted by EG and VG. The number of edges and the order of G are denoted by EG and VG, respectively. Let NGx=v∈VG:xv∈EG, NGx=NGx∪x, and dGx be the degree of x, where x∈VG. Given a subgraph F of G and X⊆VG, let NGX=∪x∈XNGx−X, NFX=NGX∩VF, NGX=∪x∈XNGx, and NFX=NGX∩VF. We simple denote dFx=NFx and NFx=NFx if X=x. When no confusion occurs, we simple identify a subgraph F of G with VF. For example, G−VF is simple and is denoted by G−F sometimes.For a graphG, let oG=odd components ofG and denote the number of edges in the maximum matching of G by α′G. Suppose i≥0; let ViG=x∈VG:dGx=i. We list the following useful results.Lemma 1.
(see [25]). LetGbe a graph; then,(1)α′G=12minG+S−oG−S:S⊆VG.Lemma 2.
(see [20]). Supposek1,…,km≥2are integers. LetGbe aPk1∪Pk2∪⋯∪Pkm-saturated graph. IfdGx=2andNGx=u,v, thenuv∈EG.
Next, we give some properties of2P4∪tP2-saturated graphs.Lemma 3.
SupposeGis2P4∪tP2-saturated withV0G≠∅; then,V1G=∅. Moreover, ifw∈V0Gandx∈VG−V0G, letFbe any copy of2P4∪tP2inG+xw; then,(2)VF⊇NGx∪x,w.Proof.
Suppose for the sake of contradiction thatx∈V1G. Since wy∉EG and G is 2P4∪tP2-saturated, G+wy has a 2P4∪tP2 containing wy. Let xy∈EG, with wy replaced by xy, and we can get a new 2P4∪tP2 in G, a contradiction. Thus, V1G=∅.
Sincexw∉EG and G is 2P4∪tP2-saturated, then G+xw has a 2P4∪tP2 containing xw and assumes F. If there exists x′∈NGx−VF, with xw replaced by xx′ in F, we can obtain a new 2P4∪tP2 in graph G, a contradiction. Therefore,(3)VF⊇NGx∪x,w.
Lemma3 is true.Lemma 4.
SupposeGis2P4∪tP2-saturated such thatV0G≠∅and all the nontrivial components are with at least4vertices. Letx∈VGsuch thatdGx=2andNGx=u,v. Then,dGu+dGv≥6. Moreover, ifdGv=3, thenNGv⊆NGu∪u.
Additionally, there does not exist a degree 2 vertexx′≠xsuch thatNGx′=u,v.Proof.
By Lemma2, we know uv∈EG. Since all the nontrivial components are with at least 4 vertices, then the triangle induced by x,u,v is not a component of G. Hence, we can assume vw∈EG for some vertex w∉x,u,v. Consequently, dGv≥3.
IfdGv=3, it is enough to show uw∈EG. If uw∉EG, G+uw has a 2P4∪tP2 containing uw, assume F. Assume v∉VF, replacing uw by uw, and we obtain a 2P4∪tP2 in G. Hence, v∈VF. If uv∈F or vw∈F or xu∈F, then x,u,v,w are selected as a P4 in F, and we can replace it with P4=xuvw, which implies there is a 2P4∪tP2 in G. So, we have uv∉F and vw∉F and xu∉F. This together with v∈VF and dGv=3 implies that xv∈F and xv is selected as a P2 in F. Now, we can claim that uw is selected as a P4 in F. Otherwise, both xv and uw are selected as a P2 in F. Replacing xv,uw in F with xu,vw, we obtain a copy of 2P4∪tP2 in G, a contradiction. If uw is selected as a middle edge in P4, then EF−uw+xu contains a 2P4∪tP2, a contradiction. If uw is selected as an end edge in P4, then EF−uw−xv+vw+xu contains a 2P4∪tP2, a contradiction.
If there exists a degree 2 vertexx′≠x such that NGx′=NGx, then select an isolated vertex y∈V0G and add the edge uy. Let F be a copy of the graph 2P4∪tP2 in G+uy. No matter uy is selected as an edge in P2 or P4 in F, since dGx=dGx′=2, we get x,x′∩VF≤1, which contradicts Lemma 3.Lemma 5.
LetGbe a2P4∪tP2-saturated graph andV0G≠∅. LetG′be an induced subgraph ofG. IfG′≅K3orG′≅K1,ℓℓ≥2, thenNGG′∩VG−VG′≠1.Proof.
Suppose, for the sake of contradiction, thatNGG′∩VG−VG′=x. Select an isolated vertex w∈V0G and add the edge wx. Since G is 2P4∪tP2-saturated, then G+wx has a 2P4∪tP2 containing wx and assumes F.
First, consider the caseG′≅K3. Suppose VG′=u1,u2,u3 and u1∈NGx. For any ui∈NGx, we have uix∉EF, where 1≤i≤3. Otherwise, VG′−VF=1 and x,w∪VG′ are selected as a P4. However, this P4 can be replaced with xu1u2u3 in F, and then, we obtain a 2P4∪tP2 in G, a contradiction. Hence, u1,u2,u3 is selected as a P2 in F. We can choose u2u3 as P2 and then replace wx in F with xu1; we obtain a 2P4∪tP2 in G, a contradiction.
Now, consider the caseG′≅K1,ℓ. Suppose u is the center of the star and VK1,ℓ=u,u1,…,uℓ. Since G is 2P4∪tP2-saturated with V0G≠∅, by Lemma 3, V1G=∅. Then, we have uix∈EG for 1≤i≤ℓ. Hence, dGui=2 and NGui=u,x for all 1≤i≤ℓ, which contradicts Lemma 4. Lemma 5 is true.


## 3. Proof of Theorem2

Before the proof of Theorem2, we discuss the property of 2P4∪tP2-saturated graph which has no components of order 2, 3, and 4.Lemma 6.
SupposeGis2P4∪tP2-saturated, but notP4∪t+2P2-saturated graph. LetV0G≠∅,H1,…,Hkbe the nontrivial components ofGandH=G∪i=1i=kVHi. IfδH≥2,|H|≥2t+8andHi≥51≤i≤k, we haveEG≥3t+10.
Moreover, if the equalityEG=3t+10holds, thenG≅Tp,q∪n−2t−8K1, wherep,q≥2andp+q=t+3.Proof.
SinceG is 2P4∪tP2-saturated, G+e has a P4∪t+2P2, where e∉EG. On the contrary, G must contain a P4∪t+2P2, since G is not P4∪t+2P2-saturated.
SupposeM is a P4∪s+2P2 in G with EM=w1w2,w2w3,w3w4∪u1v1,…,us+2vs+2. Choose M which satisfies the following:(i)
s is as large as possible(ii)
Subject to (i),∑i=1s+2dGui+dGvi is maximality
Observe thats≥t. By the choice of M, VH−VM is an independent set or an empty set. As G is 2P4∪tP2-saturated, we have(4)GVM\w1,w2,w3,w4≅s+2P2,(5)NG−VMui,vi∩NG−VMuj,vj=∅,for1≤i≠j≤s+2.
Without loss of generality, we may assumew1,w2,w3,w4⊆H1.Claim 1.
k=1.Proof.
Suppose, for the sake of contradiction, thatk≥2. Since Hi≥5 and δH≥2, we have α′Hi≥2 for every 1≤i≤k. Without loss of generality, we can assume uℓvℓ,…,umvm⊆H2, where 1≤ℓ<m≤s+2.
AsH2 is connected, there exists a path Q from ui1,vi1 to ui2,vi2 avoiding all vertices of VM\ui1,vi1,ui2,vi2 for some ℓ≤i1<i2≤m. Again, Gui1,vi1,ui2,vi2∪VQ has a P4, which, combining the edges in M−ui1vi1,ui2vi2, creates a 2P4∪sP2 in G, a contradiction. Claim 1 is true.
It follows from Claim1 that H=H1. Hence, in the rest of the proof of Lemma 6, H1 is denoted by H. Clearly, H≥2s+8≥2t+8.Claim 2.
For each1≤i≤s+2, we haveNGui,vi∩w1,w2,w3,w4≠∅.Proof.
Suppose for the sake of contradiction that there exists1≤i≤s+2 such that NGui,vi∩w1,w2,w3,w4=∅. This together with (4) implies that(6)NGui∩VM=viandNGvi∩VM=ui.
We are now ready to show that(7)dGui+dGvi≥5.
Otherwise,dGui=dGvi=2, since δH≥2. It follows from (6) that we can assume w∈NH−VMui. By Lemma 2, wvi∈EG. Then, M−uivi+uiw is a copy of P4∪s+2P2 in G. However, by Lemma 4, we have dGw≥4, and hence, dGui+dGw≥6>dGui+dGvi=4, which contradicts the choice of M. Then, we have (7) which holds.
Combining (6) and (7), there exist z1≠z2 such that z1∈NH−VMui and z2∈NH−VMvi. Then, the subgraph Gz1,ui,vi,z2 will have a P4, which, combining the edges in M−uivi, creates a 2P4∪s+1P2 in G. Since s≥t, we obtain a contradiction. Claim 2 is true.Claim 3.
There does not exist1≤i,j≤s+2such that(8)NGui,vi∩w1,w2≠∅andNGuj,vj∩w3,w4≠∅.Proof.
Suppose for the sake of contradiction that there exist1≤i,j≤s+2 such that NGui,vi∩w1,w2≠∅ and NGuj,vj∩w3,w4≠∅. By Claim 2, we may assume i≠j. However, the subgraphs Gui,vi,w1,w2 and Guj,vj,w3,w4 both contain P4, which, combining the edges in M−uivi,ujvj,w1w2,w2w3,w3w4, creates a 2P4∪sP2 in G, a contradiction. Hence, Claim 3 is true.Claim 4.
For each1≤i≤s+2, we haveNGui,vi∩w1,w2,w3,w4=1orEG>3t+10.Proof.
Suppose, for the sake of contradiction, that Claim4 is false. Then, by Claim 3 and the symmetry, we may assume EG≤3t+10 and(9)NGu1,v1∩w1,w2,w3,w4=w1,w2.
Then, by Claim3, we have(10)NGuj,vj∩w1,w2,w3,w4⊆w1,w2,for each1≤j≤s+2.Case 1.
NGu1∩w1,w2≠∅ and NGv1∩w1,w2≠∅.
Combining (9), without loss of generality, in this case, we may assume u1w1∈EG and v1w2∈EG. Now, we consider ujvj, where 2≤j≤s+2.
Ifw1∈NGuj,vj, then subgraphs Guj,vj,w1,u1 and Gv1,w2,w3,w4 both contain P4, which, combining the edges in M−u1v1,ujvj,w1w2,w2w3,w3w4, creates a 2P4∪sP2 in G, a contradiction. Hence, we have w1∉NGuj,vj. Together with Claim 2 and (10), we obtain(11)NGuj,vj∩w1,w2,w3,w4=w2.
Without loss of generality, we may assumeujw2∈EG.
IfNH−VMvj≠∅, assume G′=GNH−VMuj,vj. In order to avoid a 2P4∪tP2 in G, we get that G′≅K3 or G′≅K1,ℓℓ≥2 and NGG′∩VG−VG′=w2, which contradicts Lemma 5. Hence, NH−VMvj=∅. This together with δH≥2 and (11) implies that dGvj=2 and vjw2∈EG. As the argument of vj, we have NH−VMuj=∅. Hence, dGuj=2. Then, we can conclude that(12)dGuj=dGvj=2andNGuj∩NGvj=w2,for any1≤j≤s+2.
And, by the choice ofM, dGw3=dGw4=2. Hence, by Lemma 2, w2w4∈EG. Combining (12) implies that dGw2≥2s+3. If dGw1=2, by Lemma 2, u1w2∈EG. Hence, dGu1+dGv1+dGw1≥7. If dGw1≥3, we also have dGu1+dGv1+dGw1≥7. This together with dGw2≥2s+3, H≥2t+8, s≥t, and δH≥2 implies that 2EH≥2s+3+7+22t+4>6t+20, a contradiction.Case 2.
NGu1∩w1,w2=∅ or NGv1∩w1,w2=∅.
Combining (9), without loss of generality, in this case, we may assume NGv1∩w1,w2,w3,w4=∅. This combining δH≥2 and (4), we get NH−VMv1≠∅ and H≥2t+9. Assume v1x∈EG, where x∈H−VM. By our assumption NGu1,v1∩w1,w2,w3,w4=w1,w2, we get u1w1∈EG and u1w2∈EG. Now, we consider ujvj, where 2≤j≤s+2.
Ifw2∈NGuj,vj, then the subgraphs Guj,vj,w2,w3 and Gx,v1,u1,w1 both contain P4, which, combining the edges in M−u1v1,ujvj,w1w2,w2w3,w3w4, creates a 2P4∪sP2 in G, a contradiction. Hence, we have w2∉NGuj,vj. This together with Claim 2 and (9) implies that NGuj,vj∩w1,w2,w3,w4=w1, for any 2≤j≤s+2. Without loss of generality, we may assume ujw1∈EG. Then, we have NGx∩w1,w2,w3,w4=∅. So, by the choice of M, (5), and δH≥2, we get xu1∈EG. Hence,(13)dGu1≥4.
In order to avoid a2P4∪tP2 in G, we get that NH−VMvj=∅. This together with δH≥2 and NGuj,vj∩w1,w2,w3,w4=w1 implies that vjw1∈EG and dGvj=2. Similarly, we have dGuj=2. Therefore, ujw1∈EG and vjw1∈EG for any 2≤j≤s+2. Hence, combining s≥t implies that(14)dGw1≥2s+2≥2t+4.
And, by the choice ofM, we have dGw3=dGw4=2. Then, by Lemma 2, w2w4∈EG, which implies that(15)dGw2≥4.
Recall thatH≥2t+9 and δH≥2. Together with (13)–(15), we can get that 2EH≥2t+4+4+4+22t+6>6t+20, a contradiction. Claim 4 is true.Claim 5.
If there exists1≤i≤s+2such thatdGui+dGvi≤4, then we haveEG≥3t+10. Moreover, the equalityEG=3t+10holds if and only ifG≅Tp,q∪n−2t−8K1, wherep,q≥2andp+q=t+3.Proof.
Without loss of generality, we may assumedGu1+dGv1≤4. Since δH≥2, we have dGu1=dGv1=2. By Claim 4 and the symmetry, we complete the Claim 5 by following two cases.Case 1.NGu1,v1∩w1,w2,w3,w4=w1.SincedGu1=dGv1=2, by Lemma 2, u1w1∈EG and v1w1∈EG. By the choice of M, dGw3=dGw4=2. Also, by Lemma 2, w2w4∈EG. Now, we consider ujvj, where 2≤j≤s+2. It follows from Claim 3 and our assumption that NGuj,vj∩w1,w2,w3,w4⊆w1,w2, where 2≤j≤s+2. This together with Claim 4 implies that NGuj,vj∩w1,w2,w3,w4=wi, where i=1or2.IfNH−VMvj≠∅, assume G′=GNH−VMuj,vj. In order to avoid a 2P4∪tP2 in G, we get that G′≅K3 or G′≅K1,ℓℓ≥2 and NGG′∩VG−VG′=wi, which contradicts Lemma 5. Hence, NH−VMvj=∅. Since δH≥2, we get vjwi∈EG and dGvj=2. By the similar argument, we have NH−VMuj=∅, and hence, dGuj=2. Therefore, for each 1≤j≤s+2, we can conclude that NGuj∩NGvj=w1 or NGuj∩NGvj=w2. Together with w2w4∈EG, we have dGw1+dGw2≥2s+3+2=2s+8. Recall that s≥t, H≥2t+8, and δH≥2, we can get that 2EH≥2s+8+22t+6≥6t+20. And, if EG=3t+10, then G≅Tp,q∪n−2t−8K1, where p+q=t+3. However, if minp,q≤1, Tp,q is not a 2P4∪tP2-saturated graph, since the addition of an edge between an isolated vertex of G and the vertex of degree ΔG does not result in a 2P4∪tP2. Hence, p,q≥2; Claim 5 holds.Case 2.NGu1,v1∩w1,w2,w3,w4=w2.
SincedGu1=dGv1=2, by Lemma 2, u1w2∈EG and v1w2∈EG. By the choice of M, we have dGw3=dGw4=2. Also, by Lemma 2, w2w4∈EG. Now, we consider ujvj, where 2≤j≤s+2. It follows from Claim 3 and our assumption that NGuj,vj∩w1,w2,w3,w4⊆w1,w2.
If there exists1≤j≤s+2 such that NGuj,vj∩w1,w2,w3,w4=w1, we can claim that dGuj=dGvj=2. Otherwise, assume G′=GNH−VMuj,vj. In order to avoid a 2P4∪tP2 in G, we get that G′≅K3 or G′≅K1,ℓℓ≥2 and NGG′∩VG−VG′=w1, which contradicts Lemma 5. Then, as the similar argument in the Case 1, we can obtain EH≥3t+10, and if EG=3t+10, then G≅Tp,q, where p,q≥2 and p+q=t+3. Then, NGuj,vj∩w1,w2,w3,w4=w2, for all 1≤j≤s+2. Without loss of generality, we may assume ujw2∈EG. If NH−VMvj≠∅, assume G′=GNH−VMuj,vj. In order to avoid a 2P4∪tP2 in G, we get that G′≅K3 or G′≅K1,ℓℓ≥2 and NGG′∩VG−VG′=w2, which contradicts Lemma 5. Hence, NH−VMvj=∅. Since δH≥2, we get vjw2∈EG and dGvj=2. By the similar argument, we have NH−VMuj=∅, and hence, dGuj=2. Therefore, ujw2∈EG and vjw2∈EG for any 2≤j≤s+2. Hence,(16)dGw2≥2s+3+1≥2t+7.
This together withδH≥2, H≥2t+8, and (16) implies that 2EH≥2t+7+22t+7>6t+20. This completes the proof of Claim 5.
If there exists1≤i≤s+2 such that dGui+dGvi≤4, by Claim 5, the Lemma is proven by Claim 5. Hence, we can assume dGui+dGvi≥5 for each 1≤i≤s+2. On the contrary, by (4) and Claim 4, we can assume dVMui+dVMvi≤4. Hence, there exists xi∈NGuj,vj∩VH−VM for any 1≤i≤s+2. And, by (5), xi≠xj for 1≤i≠j≤s+2. Hence, H≥3s+2+4≥3t+10. Since δH≥2, we get EH≥3t+10. And, if the equality EG=3t+10 holds, then δH=ΔH=2 and H=3t+10, which contradicts Lemma 4. Lemma 6 is true.Lemma 7.
SupposeGis2P4∪tP2-saturated andP4∪t+2P2-saturated withV0G≠∅. LetH1,…,Hkbe the nontrivial components ofGandH=G∪i=1i=kVHi. IfδH≥2andH≥2t+8withHi≥51≤i≤k, we haveEG>3t+10.Proof.
Suppose, for the sake of contradiction, thatEG≤3t+10. Since G is 2P4∪tP2-saturated, there exists a 2P4∪tP2 in G+e for any e∉EG. Hence, α′H≥t+3. If α′H≥t+4, G must contain a copy of t+4P2. Since δH≥2 and Hi≥51≤i≤k, it is clearly that H has a P4∪t+2P2, which contradicts G is P4∪t+2P2-saturated. So, we have α′H=t+3. By Lemma 1, we obtain(17)t+3=12minH+X−oG−X:X⊆VH.
Then, we can choose a maximal subsetS⊆VH which satisfies(18)t+3=12H+S−oH−S.
SupposeH1′,…,Hp′ are the components of H−S. We have the following claims.Claim 6.
HS∪VHi′is the complete graph, where1≤i≤p.Proof.
Suppose for the sake of contradiction thatHS∪VHi′ is not a complete graph. Then, there is x,y∈S∪VHi′ with x≠y and xy∉EH. Let H′=H+xy. We have H′=H and oH′−S=oH−S. Combining (18), we obtain(19)t+3=12H′+S−oH′−S.
By Lemma1, we obtain α′H′≤t+3. Hence, G+xy has no t+4P2, contrary to G which is 2P4∪tP2-saturated. Claim 6 is true.Claim 7.
S≠∅.Proof.
Suppose for the sake of contradiction thatS=∅. Hence, H1′,…,Hp′ are all components of H. Using Claim 6, we have Hi′ is a complete graph with Hi′≥51≤i≤p. Hence, we have δH≥4 and(20)2EH=∑x∈VHdHx≥4H.
CombiningH≥2t+8, we get EH>3t+10. Hence, Claim 7 is true.
Letw∈V0G and x∈S. By Claim 6, NHx=VH−x. Let F be a 2P4∪tP2 in G+xw, using Lemma 3, we get VF⊇x,w∪NGx. Hence, we have H+1=NHx∪x,w≤VF=2t+8, contrary to G is 2P4∪tP2-saturated. Hence, Lemma 7 is true.
Now, we prove Theorem2.Proof.
of Theorem 2. Clearly,Tp,q∪aK3∪n−2t−a−8K1∈SATn,2P4∪tP2, where p≥2,q≥2, and p+q+a=t+3. Let G∈SAT¯n,2P4∪tP2; then, EG≤3t+10. Since n≥6t+12, V0G≥2. Using Lemma 3, we have V1G≠∅. Clearly, in graph G, all components of order 3 or 4 are complete. If there exists one of the components, say H1≅K4, then the addition of an edge e between an isolated vertex of G and a vertex of H1 results in a 2P4∪tP2 in G. However, the edge e can be replaced by the edge in H1, resulting in a 2P4∪tP2∈G, a contradiction. Hence, component of order 4 in G does not exist.
Now, we consider the graphG′, which is obtained by deleting all components of order 3 from G. Let a be the number of components of order 3 in G, and we obtain(21)G≅G′∪aK3.
NoteV0G′=V0G≥2. Let e be an edge joining two isolated vertices in V0G; then, there exists a 2P4∪tP2 in G+e. So, G′ has 2P4. Combining G∈SAT¯n,2P4∪tP2, we get a≤t−1. Let t′=t−a. Then, t′≥1.
AsG∈SAT¯n,2P4∪tP2, we have G′∈SATn′,2P4∪tP2, where n′=n−3a. Suppose H′ is a graph spanned by all nontrivial components of G′. Using Lemma 3, we have δH′≥2. Clearly, any component in H′ has order at least 5. Moreover, graph G′ is 2P4∪t′P2-saturated such that EG′=EG−3a≤3t′+10 and V0G′≠∅. By Lemma 6 and Lemma 7, we have H′≤2t′+7 or H′≅Tp,q∪n′−2t′−8K1, where p≥2,q≥2 and p+q=t′+3. If H′≤2t′+7, as V0G′≠∅ and G′∈SATn′,2P4∪t′P2, H′≅K2t′+7. Now, EH′=2t′+72>3t′+21, and we have EG>3t′+21+3a=3t+21>3t+10, a contradiction. Hence, H′≅Tp,q∪n′−2t′−8K1, where p≥2,q≥2, and p+q=t′+3. Combining (21), we get G≅Tp,q∪aK3∪n−2t−a−8K1, where p≥2,q≥2, and p+q+a=t+3. Hence, Theorem 2 is true.


## 4. Conclusion

Forests and trees have attracted wide attention for several reasons. Firstly, their simplicity has made some more precise results possible. Secondly, they can provide inspiration for some larger results. At present, we only know the saturation number of a few species of trees, but the saturation number of most trees is unknown.In [20], Chen et al. focused on the saturation numbers for the linear forests. They obtained an interesting set of results and proposed some conjectures. We pave the way for the following conjectures proposed by Chen et al. in [20].Conjecture 1.
(see [20]). Lett≥2be an integer. Fornsufficiently large,satn,tP3=⌊n+6t−6/2⌋.Conjecture 2.
(see [20]). Lett≥2be an integer. Fornsufficiently large,(22)satn,tP4=n+12t−122,ifnis even,n+12t−112,ifnis odd.Conjecture 3 (see [20]).
Fornsufficiently large,k≥4, andk≤ℓ≤⌈3k−2/2⌉,satn,Pk∪Pℓ=n−⌊n/ak⌋+3, where(23)ak=3⋅2m−1−2,ifk=2m,4⋅2m−1−2,ifk=2m+1.



---

*Source: 6613393-2021-05-06.xml*