# Sun Toughness Conditions forP2 and P3 Factor Uniform and Factor Critical Avoidable Graphs

Authors: Shu Gong; Haci Mehmet Baskonus; Wei Gao
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The security of a network is closely related to the structure of the network graph. The denser the network graph structure is, the better it can resist attacks. Toughness and isolated toughness are used to characterize the vulnerable programs of the network which have been paid attention from mathematics and computer scholars. On this basis, considering the particularity of the sun component structures, sun toughness was introduced in mathematics and applied to computer networks. From the perspective of modern graph theory, this paper presents the sun toughness conditions of the path factor uniform graph and the path factor critical avoidable graph inP≥2-factor and P≥3-factor settings. Furthermore, examples show that the given boundaries are sharp.


---

## Body

## 1. Introduction

Network security is one of most important focus points in computer networks. When the network is represented by a graph model, graph parameters are introduced to describe the stability and vulnerability of the network under a specific structure. The classic parameters to measure the vulnerability of a network include toughness, isolated toughness, and binding number. In this paper, we only discuss the theoretical problems in computer network such that all network structures are denoted by graphs, and only simple graphs are considered. That is to say, if there are multiple channels connected between two sites, the model will be idealized, thinking that only one edge connects two corresponding vertices.For graphG=VG,EG, we use dGx to express the degree of vertex x in G. For n≥2 being an integer number, Pn and P≥n denote the path with exactly n and at least n vertices, respectively. A path factor is a special spanning subgraph whose components are paths, and a P≥n-factor is a special path factor such that each path has at least n vertices. We no longer explain each concept of graph theory one by one since these basic notations and terminologies can be easily found in other classic graph theory books.A graphR is factor critical if any induced subgraph with order VR−1 admits a perfect matching. If H≅K1, H≅K2, or H is the corona of a factor critical graph R with VR≥3, then H is called a sun. Specially, a sun with order at least six in the last case is called a big sun. We use sunG to denote the number of sun components of G. Let ωG and iG be the number of connected components and isolated vertices of a graph G, respectively. Hence, ωG≥sunG≥iG for any graph G.Las Vergnas [1] and Kaneko [2] characterized the criterion for the existence of P≥2-factors and P≥3-factors, respectively.Lemma 1 (see Las Vergnas [1]).
A graphG contains a P≥2-factor ⇔iG−S≤2S for any vertex subset S of G.Lemma 2 (see Kaneko [2]).
A graphG contains a P≥3-factor ⇔sunG−S≤2S for any vertex subset S of G.The sun toughnesssG was introduced by Zhou et al. [3] as(1)sG=minSsunG−S:sunG−S≥2,if G is not a complete graph; otherwise, sG=+∞. Considering the previous trick of defining new toughness and isolated toughness parameters by subtracting one from the denominator, Zhu et al. [4] introduced the new parameter of sun toughness denoted by s′G which can be formulated (if G is not complete) as follows:(2)s′G=minSsunG−S−1:sunG−S≥2.For the complete graph,s′G=+∞.If for any edgee∈EG, a graph G contains a P≥n-factor covering e, then G is called a P≥n-factor covered graph. The following two conclusions for P≥n-factor covered graph for n=2 and 3 were determined by Zhang and Zhou [5].Lemma 3 (see Zhang and Zhou [5]).
A connected graphG is P≥2-factor covered ⇔(3)iG−S≤2S−ε1S,for any vertex subset S of G, where(4)ε1S=2,ifSis not an independent set,1,Sis independent and there exists a nontrivial component ofG−S,0,otherwise.Lemma 4 (see Zhang and Zhou [5]).
A connected graphG is P≥3-factor covered ⇔(5)sunG−S≤2S−ε2S,for any S⊆VG, where(6)ε2S=2,ifSis not an independent set,1,Sis independent and there exists a non−sun component ofG−S,0,otherwise.
Some recent advances in graph factors can be referred to Zhou et al. [6] and Gao et al. [7–9].The main contribution in this work is to study the existence ofP≥2-factor or P≥3-factor in special settings by means of sun toughness parameter. The results can be divided into two parts which are manifested in the next section: first, the sun toughness conditions for a graph to be P≥2-factor uniform and P≥3-factor uniform are determined; then, the sun toughness bounds for P≥2-factor avoidable graph and P≥3-factor avoidable graph are given. The counterexamples presented in sharpness section imply that all these obtained sun toughness bounds are sharp.


## 2. Main Results and Proofs

The aim of this section is to present our main conclusions and detailed proof.


### 2.1. Factor Uniform Graph

A graphG is a P≥n-factor uniform graph if for any two edges e1 and e2, G has a P≥n-factor covering e1 excluding e2 (see Zhou and Sun [10]). In this part, we study the sun toughness condition for path factor uniform graphs.Theorem 1.
LetG be a 2-edge-connected graph. If(7)sG>VG−42,ifVG≥6,1,ifVG≤5,or(8)s′G>VG−4,ifVG≥6,2,ifVG≤5,then G is a P≥2-factor uniform graph.Proof.
The 2-edge-connected condition impliesVG≥3. If VG=3, then G≅K3 and we can verify directly that K3 is a P≥2-factor uniform graph with sK3=s′K3=+∞. If VG=4, then G is isomorphic to K4 or C4 or the graph with edge set v1v2,v2v3,v3v4,v4v1,v1v3. It is easy to confirm that no matter which G is isomorphic, it is a P≥2-factor uniform graph. Therefore, for VG∈3,4, 2-edge-connected graph G is a P≥2-factor uniform graph. Next, we consider VG≥5.
For arbitrarye∈EG, G′=G−e is connected since λG≥2. To prove Theorem 1, we aim to check that G′ is P≥2-factor covered. Suppose G′ is not a P≥2-factor covered graph. By means of Lemma 3, we can find a vertex subset S of G′ satisfying(9)iG′−S≥2S−ε1S+1.
Clearly, the value ofiG′−S belongs to iG−S,iG−S+1,iG−S+2.Claim 1.
S contains at least two vertices.Proof.
IfS is an empty set, then using (9), we have iG′≥1 which contradicts to G is 2-edge-connected.
Assume thatS=1. Then, ε1S≤1, and hence iG′−S≥2 in light of (9). We get iG−S=0 since G is 2-edge-connected. It implies that K2 is a component in G−S and e is exactly an edge in K2. Suppose there is another component W in G−S with VW≥2. If VW=2, then VG≥5 and(10)12≤VG−42<sG≤SsunG−S≤12,or(11)1≤VG−4<s′G≤SsunG−S−1≤12−1=1,a contradiction. Otherwise, VW≥3, and we select VW−2 vertices from W and denote it by X such that W−X is isomorphic to K2. Thus, we have(12)VG−42<sG≤S∪XsunG−S∪X≤1+VG−52=VG−42,or(13)VG−4<s′G≤S∪XsunG−S∪X−1≤1+VG−52−1=VG−4,a contradiction.
The last situation is thatG−S is isomorphic to K2 and thus G≅K3 which is a P≥2-factor uniform graph with sK3=s′K3=+∞.
SinceS≥2 by Claim 1, we obtain ε1S≤2, iG′−S≥2S−ε1S+1≥3, iG−S≥iG′−S−2≥1, and VG≥5. The following three cases are discussed according to the relationship between iG−S and iG′−S:Case 1. iG−S=iG′−S≥3.We deduce(14)sG≤SsunG−S≤SiG−S=SiG′−S≤S2S−ε1S+1≤S2S−1.IfVG≥6, then we obtain 1≤VG−4/2<sG≤S/2S−1 which contradicts to S≥2. If VG=5, then 1<sG≤S/2S−1, also contradicts to S≥2.Fors′G, we have(15)1≤VG−4<s′G≤SsunG−S−1≤SiG′−S−1≤S2S−ε1S+1−1≤S2S−2.It impliesS<2, a contradiction.Case 2.iG−S=iG′−S−1≥2.In this case, we acquireVG≥6 and(16)1≤VG≥6−42<sG≤SsunG−S≤SiG−S=SiG′−S−1≤S2S−ε1S+1−1≤S2S−2,or(17)2≤VG−4<s′G≤SsunG−S−1≤SiG−S−1=SiG′−S−1−1≤S2S−ε1S+1−2≤S2S−3.It impliesS<2, a contradiction.Case 3.iG−S=iG′−S−2.
In this case,iG−S≥1 since iG′−S≥3. We confirm that K1 and K2 are components in G−S, e∈EK2, and VG≥5. If VG≥8, then(18)2≤VG−42<sG≤SsunG−S≤SiG−S=SiG′−S−2≤S2S−ε1S+1−2≤S2S−3,which reveals S<2, a contradiction.
IfVG=5, then G=K2∨K1∪K2 and thus sG=1 which contradicts to sG>1 if VG=5.
IfVG=6, then G=K2∨2K1∪K2 and thus sG=2/3 contradicts to sG>VG−4/2=1.
IfVG=7, then G is isomorphic to K2∨3K1∪K2 or K2∨K1∪2K2 and thus sG=1/2 or 2/3 contradicts to sG>VG−4/2=3/2.
Note thatsunG−S≥iG−S+1 because of the presence of at least one K2 component in G−S. For s′G, if VG≥6, we infer(19)2≤VG−4<s′G≤SsunG−S−1≤SiG−S=SiG′−S−2≤S2S−ε1S+1−2≤S2S−3,which reveals S<2, a contradiction. If VG=5, then G=K2∨K1∪K2 and thus s′G=2 which contradicts to s′G>2 if VG=5.
Therefore, the desired result is proved.Theorem 2.
LetG be a 2-edge-connected graph. If(20)sG>VG−42,ifVG≥6,1,ifVG≤5,or(21)s′G>VG−4,ifVG≥6,2,ifVG≤5,then G is a P≥3-factor uniform graph.Proof.
ForVG≤4, we get the conclusion in light of the corresponding discussion presented in Theorem 1. Hence, we consider VG≥5 in what follows.
For anye∈EG, G′=G−e is a connected graph in terms of λG≥2, and we prove the theorem by proving that G′ is P≥3-factor covered. Suppose that G′ is not P≥3-factor covered, and there is a subset S of VG′ satisfying(22)sunG′−S≥2S−ε2S+1.Claim 2.
S contains at least two elements.Proof.
If there is no vertex inS, then ε2S=0, sunG′=1, and G′ is a big sun. We confirm that G is a graph which is obtained by inserting an edge in a big sun. Obviously, we can select vertex set X (at least two vertices in X) from VG, such that it produces X sun components in G−X. By the definition of sun toughness, we obtain(23)1<sG≤XsunG−X≤XX=1,or(24)2<s′G≤XsunG−X−1≤XX−1=1+1X−1≤1+12−1=2,a contradiction.
IfS=1, then ε2S≤1 and sunG′−S≥2 by (22). If sunG−S≥2, then(25)1<sG≤SsunG−S≤12,or(26)2<s′G≤SsunG−S−1≤1,a contradiction.
IfsunG−S=1, then if there is a non-sun component W in G−S, it produces a new sun component after deleting e from W. Thus, there is a vertex x in W such that dG−Sx=1 and assume xy∈EG−S. We deduce sunG−S∪y≥2 and(27)1<sG≤S∪ysunG−S∪y≤1,or(28)2<s′G≤S∪ysunG−S∪y−1≤2,a contradiction. The other circumstances are described as follows: there is a K2 component in G−S, the deleting edge e is exactly belongs to EK2, and G−S−VK2 contains a non-sun component which leads ε2S=1. In this case, we have VG≥6. The worst situation is that G−S−VK2 is a complete graph Kt with order at least 3. In order to get at least two sun components, t−2 vertices need to be deleted from Kt to obtain the second K2 component. This extreme situation can be discussed using a trick similar to Claim 1 in the proofing of Theorem 1.
IfsunG−S=0, then there is a non-sun component M in G−S such that it produces two new sun components after deleting e from M. Thus, there is a vertex set Z⊆VM such that deleting Z (with Z≥1) from M will produce Z+1 sun components. We yield sunG−S∪Z≥2 and(29)1<sG≤S∪ZsunG−S∪Z=S+ZsunG−S+Z+1≤1+ZsunG′−S−2+Z+1≤1+Z2S−ε2S+1+Z−1≤1+ZZ+1=1,or(30)2<s′G≤S∪ZsunG−S∪Z−1=S+ZsunG−S+Z+1−1≤1+ZsunG′−S−2+Z≤1+Z2S−ε2S+1+Z−2≤1+ZZ=1+1Z≤2,a contradiction.
FromS≥2, we acquire ε2S≤2, sunG′−S≥3, and sunG−S≥sunG′−S−2≥1. If sunG−S=sunG′−S or sunG−S=sunG′−S−1, we deduce(31)1<sG≤SsunG−S≤SsunG′−S−1≤S2S−ε2S+1−1≤S2S−2=12+12S−2≤12+12×2−2=1,or(32)2<s′G≤SsunG−S−1≤SsunG′−S−1−1≤S2S−ε2S+1−2≤S2S−3=12+322S−3≤12+322×2−3=2,a contradiction.
IfsunG−S=sunG′−S−2, then edge e belongs to a non-sun component W in G−S, while removing e will produce two sun components. There is a vertex set X⊆VW such that deleting X (clearly X≥1) from W will produce X+1 sun components. Hence, we get(33)1<sG≤S∪XsunG−S∪X≤S+XsunG−S+X+1≤S+XsunG′−S−2+X+1≤S+X2S−ε2S+1+X−1≤S+X2S+X−2=1−S−22S+X−2≤1,a contradiction.
Fors′G, if S≥3, we obtain(34)2<s′G≤S∪XsunG−S∪X−1≤S+XsunG−S+X+1−1≤S+XsunG′−S−2+X≤S+X2S−ε2S+1+X−2≤S+X2S+X−3=1−S−32S+X−3≤1,a contradiction. If S=2, then(35)2<s′G≤S+X2S+X−3=X+2X+1=1+1X+1≤1+11+1=32,a contradiction.


### 2.2. Factor Critical Deleted Graph

A graphG is a P≥n-factor deleted graph (or called P≥n-factor avoidable graph) if for arbitrary edge e∈EG, G admits a P≥n-factor excluding e. A graph G is called a P≥n,k-factor critical deleted graph (or called P≥n,k-factor critical avoidable graph) if for any U⊆VG with U=k, G−U is a P≥n-factor deleted graph (or P≥n-factor avoidable graph).In this subsection, we present sun toughness conditions forP≥2,k-factor critical deleted graph and P≥3,k-factor critical deleted graph.Theorem 3.
Letk∈ℕ∪0 and G be a k+2-connected graph. If sG>k+2/4 (resp. s′G>k+2/3), then G is P≥2,k-factor critical deleted.Proof.
Following from connectivity condition, Theorem3 is obviously established if G is a complete graph. We only consider that G is not complete. Let U be a vertex subset with k vertices, G′=G−U, e∈EG′, and G″=G′−e. Hence, G″ is connected by means of G being k+2-connected. We prove Theorem 3 in view of proving that G″ has P≥2-factor. On the contrary, we assume that G″ has no P≥2-factor. Using Lemma 1, there is a vertex subset S of G″ satisfying(36)iG″−S≥2S+1.
Clearly,S≠∅ since G″ is connected. If S=1, then according to iG″−S=iG′−e−S≤iG′−S+2 and (36), we have iG′−S≥iG″−S−2≥2S+1−2=1. It implies that G′−S admits an isolated vertex x, and thus dGx≤dG′x+U≤dG′−Sx+S+k=k+1 which contradicts to G is k+2-connected. Therefore, S≥2.
Notice that(37)sunG−U∪S≥sunG−U∪S−e−2=sunG″−S−2≥iG″−S−2≥2S+1−2≥3.
In fact, the “ = ”s in the derivation above cannot hold simultaneously. IfsunG−U∪S=sunG−U∪S−e−2, then there is a non-sun component W in G′−S, and deleting e from W will add two new sun components in G″−S. On the other hand, if sunG″−S−2=iG″−S−2, then all sun components in G″−S are isolated vertices, and thus K2 is a sun component in G′−S and e∈EK2. Thus, sunG−U∪S=sunG−U∪S−e−2 and sunG″−S−2=iG″−S−2 cannot be hold simultaneously, and sunG−U∪S≥iG″−S−1≥2S+1−1=2S.
In light of the definition of sun toughness, we acquire(38)k+24<sG≤U∪SsunG−U∪S≤U+SiG″−S−1≤k+S2S+1−1=k+S2S=12+k2S≤12+k2×2=12+k4=k+24,or(39)k+23<s′G≤U∪SsunG−U∪S−1≤U+SiG″−S−1−1≤k+S2S+1−2=k+S2S−1=12+k+1/22S−1≤12+k+1/22×2−1=12+k+1/23=k+23,a contradiction.Theorem 4.
Letk∈ℕ∪0 and G be a k+2-connected graph. If(40)sG≥1,ifk∈0,1,>k+24,ifk≥2,resp.s′G≥1ifk=0>k+23ifk≥1,then G is P≥3,k-factor critical deleted.Proof.
Theorem4 is clearly held if G is a complete graph using connectivity condition. Only noncomplete graphs are considered in what follows. Let U be a vertex subset with k vertices, G′=G−U, e∈EG′, and G″=G′−e. Hence, G″ is connected by means of G being k+2-connected. We prove Theorem 4 in view of proving that G″ has P≥3-factor. If not, we assume that G″ has no P≥3-factor. In light of Lemma 2, there is a vertex subset S of G″ satisfying(41)sunG″−S≥2S+1.Claim 3.
S≥2.Proof.
IfS is an empty set, then using (41) and connectivity condition of G, we confirm that G″ is a big sun. Thus, VG″≥6 and let R be the factor critical subgraph of G″. We verify that R contains at least 3 vertices and G′ is constructed by inserting an edge into a big sun G″. By observation, we can select vertex set X (at least two vertices in X) from VG′, such that it produces X sun components in G′−X. Then, the contradiction can be deduced using the trick as presented in Claim 2.
IfS=1, then sunG″−S≥3 by (41) and sunG′−S≥sunG″−S−2≥1. If sunG′−S≥2, then it contradicts to G is k+2-connected.
IfsunG′−S=1, then sunG″−S=3 and there is a non-sun component W in G′−S such that it produces two new sun components after deleting e from W. It reveals that there is a sun component and a non-sun component in G′−S which contradicts to G′−S is connected.
By Claim3 and (41), we yield sunG″−S≥2S+1≥5 and sunG′−S≥sunG″−S−2≥3. Now, we consider the following cases:Case 1. sunG′−S=sunG″−S≥5.In this case, we have(42)sG≤U∪SsunG−U∪S=U+SsunG′−S=k+SsunG″−S≤k+S2S+1.Ifk=0, then 1≤sG≤k+S/2S+1<1/2, a contradiction. If k≥1, we have(43)sG≤k+S2S+1=12+k−1/22S+1≤12+k−1/22×2+1=k+25.Ifk=1, then 1≤sG≤k+2/5, a contradiction. If k≥2, then k+2/4<sG≤k+2/5, a contradiction.Fors′G, by its definition, we get(44)s′G≤U∪SsunG−U∪S−1=U+SsunG′−S−1=k+SsunG″−S−1≤k+S2S+1−1=12+k2S≤12+k2×2=k+24.Ifk=0, then 1≤s′G≤2/4, a contradiction. If k≥1, then k+2/3<s′G≤k+2/4, a contradiction.Case 2.sunG′−S=sunG″−S−1.In this case, we consider two situations. If there is a non-sun componentW in G′−S and deleting e from W, then we produce a new sun component. Then, there is a vertex y∈VW with degree 1 in G′−S, and we set xy∈EG′−S. Hence, using the definition of sun component, we have(45)sG≤U∪S∪xsunG−U∪S∪x=U+S∪xsunG′−S∪x=k+S+1sunG′−S+1=k+S+1sunG″−S−1+1≤k+S+12S+1=12+k+1/22S+1≤12+k+1/22×2+1=k+35.Ifk∈0,1, then 1≤sG≤k+3/5, a contradiction. If k≥2, then k+2/4<sG≤k+3/5 which implies k<2, a contradiction.Fors′G, we acquire(46)s′G≤U∪S∪xsunG−U∪S∪x−1=U+S∪xsunG′−S∪x−1=k+S+1sunG′−S+1−1=k+S+1sunG″−S−1≤k+S+12S+1−1=12+k+12S≤12+k+12×2=k+34.Ifk=0, then 1≤s′G≤3/4, a contradiction. If k≥1, then k+2/3<s′G≤k+3/4 which implies k<1, a contradiction.Another situation is stated as follows:K2 is a sun component in G′−S, e∈EK2, and thus the number of sun component adds 1 after removing e from G′−S. Hence, we yield(47)sG≤U∪SsunG−U∪S=U+SsunG′−S=k+SsunG″−S−1≤k+S2S+1−1=12+k2S≤12+k2×2=k+24.Ifk∈0,1, then 1≤sG≤k+2/4, a contradiction. If k≥2, then k+2/4<sG≤k+2/4, a contradiction.Fors′G, we get(48)s′G≤U∪SsunG−U∪S−1=U+SsunG′−S−1=k+SsunG″−S−1−1≤k+S2S+1−2=12+k+1/22S−1≤12+k+1/22×2−1=k+23.Ifk=0, then 1≤s′G≤2/3, a contradiction. If k≥1, then k+2/3<s′G≤k+2/3, a contradiction.Case 3. sunG′−S=sunG″−S−2.
In this case, edgee belongs to a non-sun component W in G′−S, and removing e will produce two sun components. We can find a vertex set X⊂VW such that deleting X (clearly X≥1) from W will produce X+1 sun components. Hence, in view of the definition of sun toughness, we infer(49)sG≤U∪S∪XsunG−U∪S∪X=U+S+XsunG′−S+X+1=k+S+XsunG″−S−2+X+1≤k+S+X2S+1+X−1=k+S+X2S+X=12+k+1/2X2|S|+X≤12+k+1/2X2×2+X=k+X+24+X=1+k−24+X.
Ifk=0,1, then 1≤sG≤1−2−k/4+X<1, a contradiction. If k≥2, then k+2/4<sG≤1+k−2/4+X≤1+k−2/4+1=k+3/5, which implies k<2, a contradiction.
Fors′G, we deduce(50)s′G≤U∪S∪XsunG−U∪S∪X−1=U+S+XsunG′−S+X+1−1=k+S+XsunG″−S−2+X≤k+S+X2S+1+X−2=k+S+X2S+X−1=12+k+1/2X+1/22|S|+X−1≤12+k+1/2X+1/22×2+X−1=k+X+23+X=1+k−23+X.
Ifk=0, then 1≤s′G≤1−1/3+X<1, a contradiction. If k≥1, then k+2/3<s′G≤1+k−1/3+X≤k+3/4 which reveals k<1, a contradiction.
In all, this finishes the proof of Theorem4.


## 2.1. Factor Uniform Graph

A graphG is a P≥n-factor uniform graph if for any two edges e1 and e2, G has a P≥n-factor covering e1 excluding e2 (see Zhou and Sun [10]). In this part, we study the sun toughness condition for path factor uniform graphs.Theorem 1.
LetG be a 2-edge-connected graph. If(7)sG>VG−42,ifVG≥6,1,ifVG≤5,or(8)s′G>VG−4,ifVG≥6,2,ifVG≤5,then G is a P≥2-factor uniform graph.Proof.
The 2-edge-connected condition impliesVG≥3. If VG=3, then G≅K3 and we can verify directly that K3 is a P≥2-factor uniform graph with sK3=s′K3=+∞. If VG=4, then G is isomorphic to K4 or C4 or the graph with edge set v1v2,v2v3,v3v4,v4v1,v1v3. It is easy to confirm that no matter which G is isomorphic, it is a P≥2-factor uniform graph. Therefore, for VG∈3,4, 2-edge-connected graph G is a P≥2-factor uniform graph. Next, we consider VG≥5.
For arbitrarye∈EG, G′=G−e is connected since λG≥2. To prove Theorem 1, we aim to check that G′ is P≥2-factor covered. Suppose G′ is not a P≥2-factor covered graph. By means of Lemma 3, we can find a vertex subset S of G′ satisfying(9)iG′−S≥2S−ε1S+1.
Clearly, the value ofiG′−S belongs to iG−S,iG−S+1,iG−S+2.Claim 1.
S contains at least two vertices.Proof.
IfS is an empty set, then using (9), we have iG′≥1 which contradicts to G is 2-edge-connected.
Assume thatS=1. Then, ε1S≤1, and hence iG′−S≥2 in light of (9). We get iG−S=0 since G is 2-edge-connected. It implies that K2 is a component in G−S and e is exactly an edge in K2. Suppose there is another component W in G−S with VW≥2. If VW=2, then VG≥5 and(10)12≤VG−42<sG≤SsunG−S≤12,or(11)1≤VG−4<s′G≤SsunG−S−1≤12−1=1,a contradiction. Otherwise, VW≥3, and we select VW−2 vertices from W and denote it by X such that W−X is isomorphic to K2. Thus, we have(12)VG−42<sG≤S∪XsunG−S∪X≤1+VG−52=VG−42,or(13)VG−4<s′G≤S∪XsunG−S∪X−1≤1+VG−52−1=VG−4,a contradiction.
The last situation is thatG−S is isomorphic to K2 and thus G≅K3 which is a P≥2-factor uniform graph with sK3=s′K3=+∞.
SinceS≥2 by Claim 1, we obtain ε1S≤2, iG′−S≥2S−ε1S+1≥3, iG−S≥iG′−S−2≥1, and VG≥5. The following three cases are discussed according to the relationship between iG−S and iG′−S:Case 1. iG−S=iG′−S≥3.We deduce(14)sG≤SsunG−S≤SiG−S=SiG′−S≤S2S−ε1S+1≤S2S−1.IfVG≥6, then we obtain 1≤VG−4/2<sG≤S/2S−1 which contradicts to S≥2. If VG=5, then 1<sG≤S/2S−1, also contradicts to S≥2.Fors′G, we have(15)1≤VG−4<s′G≤SsunG−S−1≤SiG′−S−1≤S2S−ε1S+1−1≤S2S−2.It impliesS<2, a contradiction.Case 2.iG−S=iG′−S−1≥2.In this case, we acquireVG≥6 and(16)1≤VG≥6−42<sG≤SsunG−S≤SiG−S=SiG′−S−1≤S2S−ε1S+1−1≤S2S−2,or(17)2≤VG−4<s′G≤SsunG−S−1≤SiG−S−1=SiG′−S−1−1≤S2S−ε1S+1−2≤S2S−3.It impliesS<2, a contradiction.Case 3.iG−S=iG′−S−2.
In this case,iG−S≥1 since iG′−S≥3. We confirm that K1 and K2 are components in G−S, e∈EK2, and VG≥5. If VG≥8, then(18)2≤VG−42<sG≤SsunG−S≤SiG−S=SiG′−S−2≤S2S−ε1S+1−2≤S2S−3,which reveals S<2, a contradiction.
IfVG=5, then G=K2∨K1∪K2 and thus sG=1 which contradicts to sG>1 if VG=5.
IfVG=6, then G=K2∨2K1∪K2 and thus sG=2/3 contradicts to sG>VG−4/2=1.
IfVG=7, then G is isomorphic to K2∨3K1∪K2 or K2∨K1∪2K2 and thus sG=1/2 or 2/3 contradicts to sG>VG−4/2=3/2.
Note thatsunG−S≥iG−S+1 because of the presence of at least one K2 component in G−S. For s′G, if VG≥6, we infer(19)2≤VG−4<s′G≤SsunG−S−1≤SiG−S=SiG′−S−2≤S2S−ε1S+1−2≤S2S−3,which reveals S<2, a contradiction. If VG=5, then G=K2∨K1∪K2 and thus s′G=2 which contradicts to s′G>2 if VG=5.
Therefore, the desired result is proved.Theorem 2.
LetG be a 2-edge-connected graph. If(20)sG>VG−42,ifVG≥6,1,ifVG≤5,or(21)s′G>VG−4,ifVG≥6,2,ifVG≤5,then G is a P≥3-factor uniform graph.Proof.
ForVG≤4, we get the conclusion in light of the corresponding discussion presented in Theorem 1. Hence, we consider VG≥5 in what follows.
For anye∈EG, G′=G−e is a connected graph in terms of λG≥2, and we prove the theorem by proving that G′ is P≥3-factor covered. Suppose that G′ is not P≥3-factor covered, and there is a subset S of VG′ satisfying(22)sunG′−S≥2S−ε2S+1.Claim 2.
S contains at least two elements.Proof.
If there is no vertex inS, then ε2S=0, sunG′=1, and G′ is a big sun. We confirm that G is a graph which is obtained by inserting an edge in a big sun. Obviously, we can select vertex set X (at least two vertices in X) from VG, such that it produces X sun components in G−X. By the definition of sun toughness, we obtain(23)1<sG≤XsunG−X≤XX=1,or(24)2<s′G≤XsunG−X−1≤XX−1=1+1X−1≤1+12−1=2,a contradiction.
IfS=1, then ε2S≤1 and sunG′−S≥2 by (22). If sunG−S≥2, then(25)1<sG≤SsunG−S≤12,or(26)2<s′G≤SsunG−S−1≤1,a contradiction.
IfsunG−S=1, then if there is a non-sun component W in G−S, it produces a new sun component after deleting e from W. Thus, there is a vertex x in W such that dG−Sx=1 and assume xy∈EG−S. We deduce sunG−S∪y≥2 and(27)1<sG≤S∪ysunG−S∪y≤1,or(28)2<s′G≤S∪ysunG−S∪y−1≤2,a contradiction. The other circumstances are described as follows: there is a K2 component in G−S, the deleting edge e is exactly belongs to EK2, and G−S−VK2 contains a non-sun component which leads ε2S=1. In this case, we have VG≥6. The worst situation is that G−S−VK2 is a complete graph Kt with order at least 3. In order to get at least two sun components, t−2 vertices need to be deleted from Kt to obtain the second K2 component. This extreme situation can be discussed using a trick similar to Claim 1 in the proofing of Theorem 1.
IfsunG−S=0, then there is a non-sun component M in G−S such that it produces two new sun components after deleting e from M. Thus, there is a vertex set Z⊆VM such that deleting Z (with Z≥1) from M will produce Z+1 sun components. We yield sunG−S∪Z≥2 and(29)1<sG≤S∪ZsunG−S∪Z=S+ZsunG−S+Z+1≤1+ZsunG′−S−2+Z+1≤1+Z2S−ε2S+1+Z−1≤1+ZZ+1=1,or(30)2<s′G≤S∪ZsunG−S∪Z−1=S+ZsunG−S+Z+1−1≤1+ZsunG′−S−2+Z≤1+Z2S−ε2S+1+Z−2≤1+ZZ=1+1Z≤2,a contradiction.
FromS≥2, we acquire ε2S≤2, sunG′−S≥3, and sunG−S≥sunG′−S−2≥1. If sunG−S=sunG′−S or sunG−S=sunG′−S−1, we deduce(31)1<sG≤SsunG−S≤SsunG′−S−1≤S2S−ε2S+1−1≤S2S−2=12+12S−2≤12+12×2−2=1,or(32)2<s′G≤SsunG−S−1≤SsunG′−S−1−1≤S2S−ε2S+1−2≤S2S−3=12+322S−3≤12+322×2−3=2,a contradiction.
IfsunG−S=sunG′−S−2, then edge e belongs to a non-sun component W in G−S, while removing e will produce two sun components. There is a vertex set X⊆VW such that deleting X (clearly X≥1) from W will produce X+1 sun components. Hence, we get(33)1<sG≤S∪XsunG−S∪X≤S+XsunG−S+X+1≤S+XsunG′−S−2+X+1≤S+X2S−ε2S+1+X−1≤S+X2S+X−2=1−S−22S+X−2≤1,a contradiction.
Fors′G, if S≥3, we obtain(34)2<s′G≤S∪XsunG−S∪X−1≤S+XsunG−S+X+1−1≤S+XsunG′−S−2+X≤S+X2S−ε2S+1+X−2≤S+X2S+X−3=1−S−32S+X−3≤1,a contradiction. If S=2, then(35)2<s′G≤S+X2S+X−3=X+2X+1=1+1X+1≤1+11+1=32,a contradiction.


## 2.2. Factor Critical Deleted Graph

A graphG is a P≥n-factor deleted graph (or called P≥n-factor avoidable graph) if for arbitrary edge e∈EG, G admits a P≥n-factor excluding e. A graph G is called a P≥n,k-factor critical deleted graph (or called P≥n,k-factor critical avoidable graph) if for any U⊆VG with U=k, G−U is a P≥n-factor deleted graph (or P≥n-factor avoidable graph).In this subsection, we present sun toughness conditions forP≥2,k-factor critical deleted graph and P≥3,k-factor critical deleted graph.Theorem 3.
Letk∈ℕ∪0 and G be a k+2-connected graph. If sG>k+2/4 (resp. s′G>k+2/3), then G is P≥2,k-factor critical deleted.Proof.
Following from connectivity condition, Theorem3 is obviously established if G is a complete graph. We only consider that G is not complete. Let U be a vertex subset with k vertices, G′=G−U, e∈EG′, and G″=G′−e. Hence, G″ is connected by means of G being k+2-connected. We prove Theorem 3 in view of proving that G″ has P≥2-factor. On the contrary, we assume that G″ has no P≥2-factor. Using Lemma 1, there is a vertex subset S of G″ satisfying(36)iG″−S≥2S+1.
Clearly,S≠∅ since G″ is connected. If S=1, then according to iG″−S=iG′−e−S≤iG′−S+2 and (36), we have iG′−S≥iG″−S−2≥2S+1−2=1. It implies that G′−S admits an isolated vertex x, and thus dGx≤dG′x+U≤dG′−Sx+S+k=k+1 which contradicts to G is k+2-connected. Therefore, S≥2.
Notice that(37)sunG−U∪S≥sunG−U∪S−e−2=sunG″−S−2≥iG″−S−2≥2S+1−2≥3.
In fact, the “ = ”s in the derivation above cannot hold simultaneously. IfsunG−U∪S=sunG−U∪S−e−2, then there is a non-sun component W in G′−S, and deleting e from W will add two new sun components in G″−S. On the other hand, if sunG″−S−2=iG″−S−2, then all sun components in G″−S are isolated vertices, and thus K2 is a sun component in G′−S and e∈EK2. Thus, sunG−U∪S=sunG−U∪S−e−2 and sunG″−S−2=iG″−S−2 cannot be hold simultaneously, and sunG−U∪S≥iG″−S−1≥2S+1−1=2S.
In light of the definition of sun toughness, we acquire(38)k+24<sG≤U∪SsunG−U∪S≤U+SiG″−S−1≤k+S2S+1−1=k+S2S=12+k2S≤12+k2×2=12+k4=k+24,or(39)k+23<s′G≤U∪SsunG−U∪S−1≤U+SiG″−S−1−1≤k+S2S+1−2=k+S2S−1=12+k+1/22S−1≤12+k+1/22×2−1=12+k+1/23=k+23,a contradiction.Theorem 4.
Letk∈ℕ∪0 and G be a k+2-connected graph. If(40)sG≥1,ifk∈0,1,>k+24,ifk≥2,resp.s′G≥1ifk=0>k+23ifk≥1,then G is P≥3,k-factor critical deleted.Proof.
Theorem4 is clearly held if G is a complete graph using connectivity condition. Only noncomplete graphs are considered in what follows. Let U be a vertex subset with k vertices, G′=G−U, e∈EG′, and G″=G′−e. Hence, G″ is connected by means of G being k+2-connected. We prove Theorem 4 in view of proving that G″ has P≥3-factor. If not, we assume that G″ has no P≥3-factor. In light of Lemma 2, there is a vertex subset S of G″ satisfying(41)sunG″−S≥2S+1.Claim 3.
S≥2.Proof.
IfS is an empty set, then using (41) and connectivity condition of G, we confirm that G″ is a big sun. Thus, VG″≥6 and let R be the factor critical subgraph of G″. We verify that R contains at least 3 vertices and G′ is constructed by inserting an edge into a big sun G″. By observation, we can select vertex set X (at least two vertices in X) from VG′, such that it produces X sun components in G′−X. Then, the contradiction can be deduced using the trick as presented in Claim 2.
IfS=1, then sunG″−S≥3 by (41) and sunG′−S≥sunG″−S−2≥1. If sunG′−S≥2, then it contradicts to G is k+2-connected.
IfsunG′−S=1, then sunG″−S=3 and there is a non-sun component W in G′−S such that it produces two new sun components after deleting e from W. It reveals that there is a sun component and a non-sun component in G′−S which contradicts to G′−S is connected.
By Claim3 and (41), we yield sunG″−S≥2S+1≥5 and sunG′−S≥sunG″−S−2≥3. Now, we consider the following cases:Case 1. sunG′−S=sunG″−S≥5.In this case, we have(42)sG≤U∪SsunG−U∪S=U+SsunG′−S=k+SsunG″−S≤k+S2S+1.Ifk=0, then 1≤sG≤k+S/2S+1<1/2, a contradiction. If k≥1, we have(43)sG≤k+S2S+1=12+k−1/22S+1≤12+k−1/22×2+1=k+25.Ifk=1, then 1≤sG≤k+2/5, a contradiction. If k≥2, then k+2/4<sG≤k+2/5, a contradiction.Fors′G, by its definition, we get(44)s′G≤U∪SsunG−U∪S−1=U+SsunG′−S−1=k+SsunG″−S−1≤k+S2S+1−1=12+k2S≤12+k2×2=k+24.Ifk=0, then 1≤s′G≤2/4, a contradiction. If k≥1, then k+2/3<s′G≤k+2/4, a contradiction.Case 2.sunG′−S=sunG″−S−1.In this case, we consider two situations. If there is a non-sun componentW in G′−S and deleting e from W, then we produce a new sun component. Then, there is a vertex y∈VW with degree 1 in G′−S, and we set xy∈EG′−S. Hence, using the definition of sun component, we have(45)sG≤U∪S∪xsunG−U∪S∪x=U+S∪xsunG′−S∪x=k+S+1sunG′−S+1=k+S+1sunG″−S−1+1≤k+S+12S+1=12+k+1/22S+1≤12+k+1/22×2+1=k+35.Ifk∈0,1, then 1≤sG≤k+3/5, a contradiction. If k≥2, then k+2/4<sG≤k+3/5 which implies k<2, a contradiction.Fors′G, we acquire(46)s′G≤U∪S∪xsunG−U∪S∪x−1=U+S∪xsunG′−S∪x−1=k+S+1sunG′−S+1−1=k+S+1sunG″−S−1≤k+S+12S+1−1=12+k+12S≤12+k+12×2=k+34.Ifk=0, then 1≤s′G≤3/4, a contradiction. If k≥1, then k+2/3<s′G≤k+3/4 which implies k<1, a contradiction.Another situation is stated as follows:K2 is a sun component in G′−S, e∈EK2, and thus the number of sun component adds 1 after removing e from G′−S. Hence, we yield(47)sG≤U∪SsunG−U∪S=U+SsunG′−S=k+SsunG″−S−1≤k+S2S+1−1=12+k2S≤12+k2×2=k+24.Ifk∈0,1, then 1≤sG≤k+2/4, a contradiction. If k≥2, then k+2/4<sG≤k+2/4, a contradiction.Fors′G, we get(48)s′G≤U∪SsunG−U∪S−1=U+SsunG′−S−1=k+SsunG″−S−1−1≤k+S2S+1−2=12+k+1/22S−1≤12+k+1/22×2−1=k+23.Ifk=0, then 1≤s′G≤2/3, a contradiction. If k≥1, then k+2/3<s′G≤k+2/3, a contradiction.Case 3. sunG′−S=sunG″−S−2.
In this case, edgee belongs to a non-sun component W in G′−S, and removing e will produce two sun components. We can find a vertex set X⊂VW such that deleting X (clearly X≥1) from W will produce X+1 sun components. Hence, in view of the definition of sun toughness, we infer(49)sG≤U∪S∪XsunG−U∪S∪X=U+S+XsunG′−S+X+1=k+S+XsunG″−S−2+X+1≤k+S+X2S+1+X−1=k+S+X2S+X=12+k+1/2X2|S|+X≤12+k+1/2X2×2+X=k+X+24+X=1+k−24+X.
Ifk=0,1, then 1≤sG≤1−2−k/4+X<1, a contradiction. If k≥2, then k+2/4<sG≤1+k−2/4+X≤1+k−2/4+1=k+3/5, which implies k<2, a contradiction.
Fors′G, we deduce(50)s′G≤U∪S∪XsunG−U∪S∪X−1=U+S+XsunG′−S+X+1−1=k+S+XsunG″−S−2+X≤k+S+X2S+1+X−2=k+S+X2S+X−1=12+k+1/2X+1/22|S|+X−1≤12+k+1/2X+1/22×2+X−1=k+X+23+X=1+k−23+X.
Ifk=0, then 1≤s′G≤1−1/3+X<1, a contradiction. If k≥1, then k+2/3<s′G≤1+k−1/3+X≤k+3/4 which reveals k<1, a contradiction.
In all, this finishes the proof of Theorem4.


## 3. Sharpness

### 3.1. Sharpness of Theorems1 and 2

The sun toughness bounds in Theorems1 and 2 are tight. For VG≥6, set G=K1∨K2∪Kt which is 2-edge-connected graph where t≥3 and thus Kt is not a sun. Select t−2 vertices in Kt and denote this vertex set by X. We yield(51)sG=VK1∪XsunG−VK1∪X=1+VG−52=VG−42,s′G=VK1∪XsunG−VK1∪X−1=1+VG−52−1=VG−4.Selecte∈EK2 and set G′=G−e=K1∨2K1∪Kt. Let S be the vertex set in first K1 in G′. We have ε1S=ε2S=1,(52)iG′−S=2>1=2S−ε1S,sunG′−S=2>1=2S−ε2S.Hence, in view of Lemmas3 and 4, G′ is neither P≥2-factor covered nor P≥3-factor covered, and G is neither a P≥2-factor uniform graph nor a P≥3-factor uniform graph.ForVG=5, we consider G=K2∨K1∪K2. Clearly, sG=1 and s′G=2. Choose e∈EK1∪K2 and G′=G−e=K2∨3K1. Set S=VK2 in G′ and then ε1S=ε2S=2,(53)iG′−S=3>2=2S−ε1S,sunG′−S=3>2=2S−ε2S.Therefore, in light of Lemmas3 and 4, G′ is neither P≥2-factor covered nor P≥3-factor covered and G is neither a P≥2-factor uniform graph nor a P≥3-factor uniform graph.


### 3.2. Sharpness of Theorem3

To state the sharpness of Theorem3, we consider graph G=Kk+2∨K2∪3K1. Clearly, G is k+2-connected graph, sG=k+2/4, and s′G=k+2/3. Let U⊂VKk+2 with U=k and e∈EK2. Then, G−U−e=K2∨5K1. Set S=VK2⊂VG−U−e, and we have(54)iG−U−e−S=5>4=2S.Thus,G−U−e has no P≥2-factor, G−U is not a P≥2-factor avoidable graph, and G is not a P≥2,k-factor critical avoidable graph.


### 3.3. Sharpness of Theorem4

We use the following graphs to show that the sun toughness bounds described in Theorem4 are tight. First, considering G=Kk+2∨3K2∪W where the subgraph W is constructed as Figure 1, there are two big suns H1 and H2 connected by an edge e, and W is a non-sun component in G−VKk+2.Figure 1
The structure ofW.LetR1 and R2 be the factor critical subgraph of W where both VR1 and VR2 are big numbers. We confirm that(55)sG=VKk+2∪VR1∪VR2−wsunG−VKk+2∪VR1∪VR2−w=k+2+VR1+VR2−13+VR1+VR2=1+k−23+VR1+VR2,which implies that if k<2, then sG<1, and sG⟶1 as VR1+VR2⟶+∞.Also, we verify(56)s′G=VKk+2∪VR1∪VR2−wsunG−VKk+2∪VR1∪VR2−w−1=k+2+VR1+VR2−13+VR1+VR2−1=1+k−12+VR1+VR2,which implies that if k<1, then s′G<1, and s′G⟶1 as VR1+VR2⟶+∞.LetU⊂VKk+2 with U=k, G′=G−U=K2∨3K2∪W, e∈EW be the edge which connects two big suns, and G″=G′−e=K2∨3K2∪H1∪H2. Let S=VK2 (the first K2 which belongs to Kk+2 in G) and G″−S=3K2∪H1∪H2. We have(57)sunG″−S=5>4=2S.Hence, by means of Lemma2, G″ has no P3-factor, G′ is not a P≥3-factor avoidable graph, and G is not a P≥3,k-factor critical avoidable graph. Therefore, the sG bound for k=0 or 1 and s′G bound for k=0 in Theorem 4 are tight.Last, we consider graphG=Kk+2∨4K2. Clearly, we have sG=k+2/4 and s′G=k+2/3. Let U⊂VKk+2 with U=k, G′=G−U=K2∨4K2, e∈E4K2, and G″=G′−e=K2∨3K2∪2K1. Let S=VK2 (the first K2 which belongs to Kk+2 in G) and G″−S=3K2∪2K1. We obtain(58)sunG″−S=5>4=2S.Thus, according to Lemma2, G″ has no P3-factor, G′ is not a P≥3-factor avoidable graph, and G is not a P≥3,k-factor critical avoidable graph. That is to say, the sG bound for k≥2 and s′G bound for k≥1 in Theorem 4 are tight.


## 3.1. Sharpness of Theorems1 and 2

The sun toughness bounds in Theorems1 and 2 are tight. For VG≥6, set G=K1∨K2∪Kt which is 2-edge-connected graph where t≥3 and thus Kt is not a sun. Select t−2 vertices in Kt and denote this vertex set by X. We yield(51)sG=VK1∪XsunG−VK1∪X=1+VG−52=VG−42,s′G=VK1∪XsunG−VK1∪X−1=1+VG−52−1=VG−4.Selecte∈EK2 and set G′=G−e=K1∨2K1∪Kt. Let S be the vertex set in first K1 in G′. We have ε1S=ε2S=1,(52)iG′−S=2>1=2S−ε1S,sunG′−S=2>1=2S−ε2S.Hence, in view of Lemmas3 and 4, G′ is neither P≥2-factor covered nor P≥3-factor covered, and G is neither a P≥2-factor uniform graph nor a P≥3-factor uniform graph.ForVG=5, we consider G=K2∨K1∪K2. Clearly, sG=1 and s′G=2. Choose e∈EK1∪K2 and G′=G−e=K2∨3K1. Set S=VK2 in G′ and then ε1S=ε2S=2,(53)iG′−S=3>2=2S−ε1S,sunG′−S=3>2=2S−ε2S.Therefore, in light of Lemmas3 and 4, G′ is neither P≥2-factor covered nor P≥3-factor covered and G is neither a P≥2-factor uniform graph nor a P≥3-factor uniform graph.


## 3.2. Sharpness of Theorem3

To state the sharpness of Theorem3, we consider graph G=Kk+2∨K2∪3K1. Clearly, G is k+2-connected graph, sG=k+2/4, and s′G=k+2/3. Let U⊂VKk+2 with U=k and e∈EK2. Then, G−U−e=K2∨5K1. Set S=VK2⊂VG−U−e, and we have(54)iG−U−e−S=5>4=2S.Thus,G−U−e has no P≥2-factor, G−U is not a P≥2-factor avoidable graph, and G is not a P≥2,k-factor critical avoidable graph.


## 3.3. Sharpness of Theorem4

We use the following graphs to show that the sun toughness bounds described in Theorem4 are tight. First, considering G=Kk+2∨3K2∪W where the subgraph W is constructed as Figure 1, there are two big suns H1 and H2 connected by an edge e, and W is a non-sun component in G−VKk+2.Figure 1
The structure ofW.LetR1 and R2 be the factor critical subgraph of W where both VR1 and VR2 are big numbers. We confirm that(55)sG=VKk+2∪VR1∪VR2−wsunG−VKk+2∪VR1∪VR2−w=k+2+VR1+VR2−13+VR1+VR2=1+k−23+VR1+VR2,which implies that if k<2, then sG<1, and sG⟶1 as VR1+VR2⟶+∞.Also, we verify(56)s′G=VKk+2∪VR1∪VR2−wsunG−VKk+2∪VR1∪VR2−w−1=k+2+VR1+VR2−13+VR1+VR2−1=1+k−12+VR1+VR2,which implies that if k<1, then s′G<1, and s′G⟶1 as VR1+VR2⟶+∞.LetU⊂VKk+2 with U=k, G′=G−U=K2∨3K2∪W, e∈EW be the edge which connects two big suns, and G″=G′−e=K2∨3K2∪H1∪H2. Let S=VK2 (the first K2 which belongs to Kk+2 in G) and G″−S=3K2∪H1∪H2. We have(57)sunG″−S=5>4=2S.Hence, by means of Lemma2, G″ has no P3-factor, G′ is not a P≥3-factor avoidable graph, and G is not a P≥3,k-factor critical avoidable graph. Therefore, the sG bound for k=0 or 1 and s′G bound for k=0 in Theorem 4 are tight.Last, we consider graphG=Kk+2∨4K2. Clearly, we have sG=k+2/4 and s′G=k+2/3. Let U⊂VKk+2 with U=k, G′=G−U=K2∨4K2, e∈E4K2, and G″=G′−e=K2∨3K2∪2K1. Let S=VK2 (the first K2 which belongs to Kk+2 in G) and G″−S=3K2∪2K1. We obtain(58)sunG″−S=5>4=2S.Thus, according to Lemma2, G″ has no P3-factor, G′ is not a P≥3-factor avoidable graph, and G is not a P≥3,k-factor critical avoidable graph. That is to say, the sG bound for k≥2 and s′G bound for k≥1 in Theorem 4 are tight.


## 4. Conclusion

In our article, the relationship between sun toughness and the existence of path factor in particular settings is studied. The theorems yielded in this paper belong to existence theorems, i.e., under what kind of conditions the path factor exists. However, in a specific computer network, it needs to use a certain algorithm to determine the value of sun toughness of the fix network graph and give the eligible path factor on the graph from the algorithm point of view. The problems of such algorithms are worthy of consideration in the future research.



---

*Source: 5526335-2021-10-18.xml*