# Vertex-Disjoint Paths in a 3-Aryn-Cube with Faulty Vertices

Authors: Xiaolei Ma; Shiying Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The construction of vertex-disjoint paths (disjoint paths) is an important research topic in various kinds of interconnection networks, which can improve the transmission rate and reliability. Thek-ary n-cube is a family of popular networks. In this paper, we determine that there are m2≤m≤n disjoint paths in 3-ary n-cube covering Qn3−F from S to T (many-to-many) with F≤2n−2m and from s to T (one-to-many) with F≤2n−m−1 where s is in a fault-free cycle of length three.


---

## Body

## 1. Introduction

Vertex-disjoint paths (disjoint paths for short) are a set of paths in a graph that they do not share any vertices. A disjoint path cover of a graph is a disjoint path between two different vertices, and it covers all vertices of the graph. The disjoint path cover problem has been applied in many fields such as software testing, database design, and code optimization. Actually, vertex-disjoint paths can accelerate data transmission by providing parallel communication paths to avoid communication congestion. Besides, disjoint paths enhance the robustness of vertex failure and load balancing capability [1] and accelerate the transmission of large amounts of data by splitting data into disjoint communication paths of multiple vertices. The problem of many-to-many disjoint paths is an important problem in networks. It has attracted much attention because of its application in fault-tolerant routings for high-performance interconnection network.Depending on the number of sources or sinks, there are one-to-one, one-to-many, and many-to-many disjoint paths problems. Among them, the one-to-one disjoint path is what we usually call the Hamilton path problem. A nonbipartite graphG is one-to-one m-disjoint path coverable if there is an m-disjoint path cover between any two vertices of G. A bipartite graph is one-to-one m-disjoint path coverable if there is an m-disjoint path cover between any two vertices in different partite sets. Shih and Kao [1] constructed the one-to-one m-disjoint path cover of k-ary n-cube for 1≤m≤2n, n≥2 and k≥3. Li et al. [2] studied many-to-many k-disjoint paths in hypercubes with f≤2n−2k−2, 1≤k≤n−1 and each fault-free vertex has at least two fault-free neighbors. Chen in [3] considered many-to-many k disjoint S,T-paths in the hypercube with fv+fe≤n−k−1, 1≤k≤n−1 and any two sets S and T of k fault-free vertices in different parts. Zhang and Wang [4] proved that many-to-many m disjoint paths cover in k-ary n-cubes with even k≥4 and 1≤m≤2n−1. So, we consider some disjoint path problems about 3-ary n-cubes. There is also research on other graphs. Such as one-to-many disjoint paths of n,k-star graph [5] and hyper-star networks [6] and one-to-one disjoint path covers on alternating group graphs [7].For a setS=s1,s2,…,sk of k sources and a set T=t1,t2,…,tk of k sinks in VG with S∩T=∅, the many-to-many k-disjoint path problem is to determine whether there exist k disjoint paths each joining a source and a sink. In other words, we need to find k disjoint paths P1,P2,…,Pk in G joining S and T, which cover all the vertices in the graph; that is, ∪1≤i≤kVPi=VG and VPi∩VPj=∅ for i≠j and 1≤i,j≤k. In addition, this problem is also subclassified into paired and unpaired types. In paired type, each source should be joined to a specific sink; that is, si should be joined to ti. Otherwise, each source can be joined to an arbitrary sink; that is, si could be joined to tj for i≠j. We study the unpaired type in this paper. Specially, if S=s, then it is called one-to-many disjoint paths; that is, VPi∩VPj=s for all i≠j and 1≤i,j≤k.With the development of science and the expansion of the scale of computer system, people have more higher requirements for the reliability of network. However, computer failure is inevitable in a system. So, the disjoint path cover problem is also extended to a graph with some faulty elementsF (vertices and/or edges). A graph G is called f-fault hamiltonian-connected if each pair of vertices are joined by a hamiltonian path in G−F for any faulty elements F≤f.In this paper, we studym disjoint paths of 3-ary n-cube covering Qn3−F with faulty vertices F≤2n−2m from S to T for S=T=m in Theorem 1. Besides, we also consider m disjoint paths of 3-ary n-cube covering Qn3−F with faulty vertices F≤2n−m−1 from s to T where T=m and s is in a fault-free cycle of length three in Theorem 2.


## 2. Preliminaries

### 2.1. Notations

An interconnection network can be represented by a graphG=V,E, where V represents the vertex set and E represents the edge set. Let G be a simple undirected graph. For a vertex v, NGv is the set of vertices adjacent to v in G. The path P=v1,v2,…,vn−1,vn is a sequence of adjacent vertices where all the vertices are distinct, which is denoted by P=v1,vn. If the path P satisfies v1=vn, it is called a cycle. In addition, P−1=vn,vn−1,…,v2,v1. For 1≤i<j≤n, Pvi,vj denotes the section from vi to vj in P. For uv1,vnw∈E, uv1∪P∪vnw=u,v1,…,vn−1,vn,w. A path or cycle which contains every vertex of a graph is called a Hamilton path (hamiltonian path) or Hamilton cycle (hamiltonian cycle) of the graph. A graph is hamiltonian if it contains a Hamilton cycle. A graph is hamiltonian-connected if there exists a Hamilton path between any two distinct vertices of the graph. For graph-theoretical terminology and notation not defined here, we follow [8].


### 2.2. Thek-Ary n-Cube Qnk

Definition 1.
Thek-ary n-cube Qnkn≥1 is a graph with kn vertices, each of which has the form u=un−1un−2…u0, where 0≤ui≤k−1 for every 0≤i≤n−1. Two vertices u=un−1un−2…u0 and v=vn−1vn−2…v0 in Qnk are adjacent if and only if there exists an integer j, 0≤j≤n−1, such that uj=vj±1modk and ui=vi for every i∈0,1,…,n−1\j. For clarity of presentation, we omit writing “modk” in similar expressions for the remainder of the paper.
We discuss the 3-aryn-cube Qn3 with 2n regular. Obviously, Q13 is a cycle of length 3, and Q23 is a 3×3 wrap-around mesh. We can partition Qn3 along j-dimension, 0≤j≤n−1, by deleting all the j-dimension edges, into three disjoint subcubes, Qn30, Qn31 and Qn32 (abbreviated as Q0, Q1 and Q2, if there are no ambiguities). Qj is isomorphic to Qn−13 for 0≤j≤2. For 0≤i,j≤2 and i≠j, the edge set between Qi and Qj is a perfect matching.Lemma 1 (see [9]).
Thek-ary n-cube is hamiltonian-connected when k is odd.Lemma 2 (see [10]).
Assumek is odd with k≥3. Let F be a set of faulty vertices and/or edges in a k-ary n-cube Qnk.(1)
IfF≤2n−2, then the graph Qnk−F is hamiltonian.(2)
IfF≤2n−3, then the graph Qnk−F is hamiltonian-connected.Lemma 3 (see [11]).
Letn≥2, F⊂VQn3, F≤2n−4. If s1,t1,s2,t2 are four vertices in Qn3−F, then there are two vertex-disjoint paths P1=s1,t1 and P2=s2,t2 such that VP1∪VP2=VQn3−F.


## 2.1. Notations

An interconnection network can be represented by a graphG=V,E, where V represents the vertex set and E represents the edge set. Let G be a simple undirected graph. For a vertex v, NGv is the set of vertices adjacent to v in G. The path P=v1,v2,…,vn−1,vn is a sequence of adjacent vertices where all the vertices are distinct, which is denoted by P=v1,vn. If the path P satisfies v1=vn, it is called a cycle. In addition, P−1=vn,vn−1,…,v2,v1. For 1≤i<j≤n, Pvi,vj denotes the section from vi to vj in P. For uv1,vnw∈E, uv1∪P∪vnw=u,v1,…,vn−1,vn,w. A path or cycle which contains every vertex of a graph is called a Hamilton path (hamiltonian path) or Hamilton cycle (hamiltonian cycle) of the graph. A graph is hamiltonian if it contains a Hamilton cycle. A graph is hamiltonian-connected if there exists a Hamilton path between any two distinct vertices of the graph. For graph-theoretical terminology and notation not defined here, we follow [8].


## 2.2. Thek-Ary n-Cube Qnk

Definition 1.
Thek-ary n-cube Qnkn≥1 is a graph with kn vertices, each of which has the form u=un−1un−2…u0, where 0≤ui≤k−1 for every 0≤i≤n−1. Two vertices u=un−1un−2…u0 and v=vn−1vn−2…v0 in Qnk are adjacent if and only if there exists an integer j, 0≤j≤n−1, such that uj=vj±1modk and ui=vi for every i∈0,1,…,n−1\j. For clarity of presentation, we omit writing “modk” in similar expressions for the remainder of the paper.
We discuss the 3-aryn-cube Qn3 with 2n regular. Obviously, Q13 is a cycle of length 3, and Q23 is a 3×3 wrap-around mesh. We can partition Qn3 along j-dimension, 0≤j≤n−1, by deleting all the j-dimension edges, into three disjoint subcubes, Qn30, Qn31 and Qn32 (abbreviated as Q0, Q1 and Q2, if there are no ambiguities). Qj is isomorphic to Qn−13 for 0≤j≤2. For 0≤i,j≤2 and i≠j, the edge set between Qi and Qj is a perfect matching.Lemma 1 (see [9]).
Thek-ary n-cube is hamiltonian-connected when k is odd.Lemma 2 (see [10]).
Assumek is odd with k≥3. Let F be a set of faulty vertices and/or edges in a k-ary n-cube Qnk.(1)
IfF≤2n−2, then the graph Qnk−F is hamiltonian.(2)
IfF≤2n−3, then the graph Qnk−F is hamiltonian-connected.Lemma 3 (see [11]).
Letn≥2, F⊂VQn3, F≤2n−4. If s1,t1,s2,t2 are four vertices in Qn3−F, then there are two vertex-disjoint paths P1=s1,t1 and P2=s2,t2 such that VP1∪VP2=VQn3−F.


## 3. Many-to-Many Disjoint Paths

Theorem 1.
LetQn3 be a 3-ary n-cube for n≥2. Let F be a vertex faulty set of Qn3. Let S,T⊂VQn3 with 2≤S=T=m≤n. If F≤2n−2m, then there are m disjoint paths from S to T covering Qn3−F.Proof.
We prove the theorem by induction onm. When m=2, S=T=2 and F≤2n−4. By Lemma 3, the theorem holds. Assume the theorem holds on m−1. We prove the theorem holds on m for n≥m≥3.
Suppose there issitj∈EQn3 for 1≤i,j≤m. Note F∪si,tj≤2n−2m+2=2n−2m−1. By the induction hypothesis, there are m−1 disjoint paths Pk1≤k≤m−1 from S\si to T\tj covering Qn3−F−si,tj. Let Pm=si,tj. Then, the theorem holds. Thus, we suppose sitj∉EQn3 for all 1≤i,j≤m.
We decomposeQn3 into three isomorphic subgraphs Q0,Q1,Q2 along one dimension. Let Fi=F∩VQi, Si=S∩VQi and Ti=T∩VQi for 0≤i≤2. Let S=s1,…,sm and T=t1,…,tm. If si,ti∈VQj for 1≤i≤m and 0≤j≤2, then let sik=Nsi∩VQk and tik=Nti∩VQk for k∈0,1,2\j.Case 1.Si=Ti for all 0≤i≤2.Case 1.1.Si=Ti=m for some 0≤i≤2.Without loss of generality, letS0=T0=m. Then, S1=S2=T1=T2=0. Let S0=s1,…,sm and T0=t1,…,tm.Case 1.1.1.F0=2n−2m.Then,F1=F2=0. Let S0′=S0\sm and T0′=T0\tm. Then, S0′=T0′=m−1. By the induction hypothesis, there are m−1 disjoint paths Ri=si,ti1≤i≤m−1 from S0′ to T0′ covering Q0−F0−sm−tm. Then, sm,tm∈∪i=1m−1VRi.Case 1.1.1.1.sm,tm∈VRi for some 1≤i≤m−1.Without loss of generality, letsm,tm∈VR1. Suppose sm is before tm in R1. Then, R1=R1s1,sm∪R1sm,tm∪R1tm,t1. Let u (resp. v) be the before vertex (resp. later vertex) of sm (resp. tm) in R1. Let u1=Nu∩VQ1 and v1=Nv∩VQ1. By Lemma 1, there is a Hamilton path L=u1,v1 in Q1. Let xy∈EL, x2=Nx∩VQ2 and y2=Ny∩VQ2. By Lemma 1, there is a Hamilton path M=x2,y2 in Q2. Let P1=R1s1,u∪uu1,vv1∪L−xy∪xx2,yy2∪M∪R1v,t1, Pi=Ri2≤i≤m−1 and Pm=R1sm,tm. Similarly, tm is before sm in R1.Case 1.1.1.2.sm∈VRi,tm∈VRj for 1≤i,j≤m−1 and i≠j.Without loss of generality, letsm∈VR1 and tm∈VR2. Let u and v be the before and later vertex of sm in R1, respectively. Let u1=Nu∩VQ1 and v1=Nv∩VQ1. Let x and y be the before and later vertex of tm in R2, respectively. Let x1=Nx∩VQ1 and y1=Ny∩VQ1. Note F1=0≤2n−6 for n≥3. By Lemma 3, there are two disjoint paths L1=u1,v1 and L2=x1,y1 covering Q1−F1. By Lemma 1, there is a Hamilton path M=sm2,tm2 in Q2. Let P1=R1−sm∪uu1,vv1∪L1, P2=R2−tm∪xx1,yy1∪L2, Pi=Ri3≤i≤m−1 and Pm=smsm2,tmtm2∪M.Case 1.1.2.F0=2n−2m−1.Then,F1∪F2≤1. Without loss of generality, let F1=0 and F2≤1. Let S0′=S0\sm and T0′=T0\tm. Then, S0′=T0′=m−1. Note F0∪tm=2n−2m. By the induction hypothesis, there are m−1 disjoint paths Ri=si,ti1≤i≤m−1 from S0′ to T0′ covering Q0−F0−tm. Then, sm∈VRi for some 1≤i≤m−1. Without loss of generality, let sm∈VR1. Then, R1=R1s1,sm∪R1sm,t1. Let u and v be the before and later vertex of sm in R1, respectively. Let ui=Nu∩VQi and vi=Nv∩VQi for 1≤i≤2.Ifu2∈F2 or v2∈F2, then sm2∉F2 and tm2∉F2. By Lemma 2, there is a path L1=u1,v1 and M1=sm2,tm2 covering Q1−F1 and Q2−F2, respectively. Let P1=R1−sm∪uu1,vv1∪L1, Pi=Ri2≤i≤m−1 and Pm=smsm2,tmtm2∪M1.Supposeu2∉F2 and v2∉F2. By Lemma 2, there is a path L2=sm1,tm1 and M2=u2,v2 covering Q1−F1 and Q2−F2, respectively. Let P1=R1−sm∪uu2,vv2∪M2, Pi=Ri2≤i≤m−1 and Pm=smsm1,tmtm1∪L2.Case 1.1.3.2n−2m−3≤F0≤2n−2m−2.In this case,2n−2m−2≥0. We get n≥m+1≥4 for m≥3. We have F1∪F2≤3. Without loss of generality, let F1≤⌊3/2⌋=1. Since S=T=m≥3>1≥F1, there are two vertices si1,ti1∉F1 for some 1≤i≤m. Without loss of generality, let sm1,tm1∉F1. Let S0′=S0\sm and T0′=T0\tm. Then, S0′=T0′=m−1. Note F0∪sm,tm≤2n−2m. By the induction hypothesis, there are m−1 disjoint paths Pi=si,ti1≤i≤m−1 from S0′ to T0′ covering Q0−F0−sm−tm. Since VQ1−F1∪F2−sm1,tm1≥3n−1−3−2≥4 for n≥3, there are two edges x1x2 and y1y2 such that xi,yi⊂VQi−Fi−sm1,tm1 for 1≤i≤2. Note F1≤1≤2n−6 for n≥4. By Lemma 3, there are two disjoint paths L1=sm1,x1 and L2=y1,tm1 covering Q1−F1. Note F2≤3≤2n−5 for n≥4. By Lemma 2, there is a path M=x2,y2 covering Q2−F2. Let Pm=smsm1∪L1∪x1x2∪M∪y2y1∪L2∪tm1tm.Case 1.1.4.F0≤2n−2m−4.LetNQ0sm=u1,…,u2n−2 and uij=Nui∩VQj for 1≤i≤2n−2 and j=1,2. Since NQ0sm−S\sm=2n−2−m−1>2n−2m≥F for m≥3, there is an edge uiui1 such that ui∈VQ0−F0−S and ui1∈VQ1−F1 for 1≤i≤2n−2. Without loss of generality, let u1u11 be satisfied. Let NQ0ti=v1,…,v2n−2 and vij=Nvi∩VQj for 1≤i≤2n−2 and j=1,2. Since NQ0tm−T\tm−u1≥2n−2−m−1−1>2n−2m≥F for m≥3, there is an edge vivi1 such that vi∈VQ0−F0−u1 and vi1∈VQ1−F1−u11 for 1≤i≤2n−2. Without loss of generality, let v1v11 be satisfied.NoteF0∪sm,tm,u1,v1≤2n−2m. By the induction hypothesis, there are m−1 disjoint paths Pi=si,ti1≤i≤m−1 covering. Since VQ1−F−u11,v11≥3n−1−2n−2m−2≥7 for 3≤m≤n, there are two edges x1x2, y1y2 such that xi,yi⊂VQi−Fi−u11,v11 for i=1,2. Note F1≤2n−2m≤2n−6 for m≥3. By Lemma 3, there are two disjoint paths L1=u11,x1 and L2=y1,v11 covering Q1−F1. Note F2≤2n−2m<2n−5 for m≥3. By Lemma 2, there is a path M=x2,y2 covering Q2−F2. Let Pm=smu1,u1u11,tmv1,v1v11∪L1∪L2∪x1x2,y1y2∪M.Case 1.2.Si=Ti=m−1 for some 0≤i≤2.Without loss of generality, letS0=T0=1, S1=T1=m−1 and S2=T2=0. Let S0=s1, T0=t1, S1=s2,…,sm and T1=t2,…,tm. By the induction hypothesis, there are m−1 disjoint paths Pi=si,ti2≤i≤m covering Q1−F1. Since VQi−F−S0−T0≥3n−1−2n−2m−2≥7 for 3≤m≤n, there are two edges x1x2, y1y2 such that xi,yi⊂VQi−Fi−S0−T0 for i=0,2. Note F0≤2n−2m≤2n−6 for m≥3. By Lemma 3, there are two disjoint paths R1=s1,x0 and R2=y0,t1 covering Q0−F0. By Lemma 2, there is a path M=x2,y2 covering Q2−F2. Let P1=R1∪x0x2∪M∪y0y2∪R2.Case 1.3.1≤Si=Ti≤m−2 for all 0≤i≤2.LetSi=Ti=pi≤m−2 for 0≤i≤2. Then, p0+p1+p2=m. Note Fi≤2n−2m≤2n−1−2pi. By the induction hypothesis, there are pi disjoint paths covering Qi−Fi for 0≤i≤2.Case 1.4.Si=Ti=0 for only one 0≤i≤2.LetS0=T0=0. If there is Si=Ti=m−1 or Si=Ti=1 for some 1≤i≤2, then it is similar to Case 1.2. Thus, suppose 2≤Si=Ti≤m−2 for 1≤i≤2. Let S1=T1=p. Then, S2=T2=m−p. Let S1=s1,…,sp, T1=t1,…,tp, S2=sp+1,…,sm and T2=tp+1,…,tm. Note S1=T1=p≤m−2. By the induction hypothesis, there are p disjoint paths Pi=si,ti1≤i≤p covering Q1−F1.SinceVQi−F−S−T≥3n−1−2n−2m−2m≥3 for n≥3, there are two edges u0u2,v0v2 such that ui,vi∈VQi−F−S−T for i=0,2. Note S2∪v2=T2∪u2=m−p+1≤m−1. By the induction hypothesis, there are m−p+1 disjoint paths Pi=si,tip+1≤i≤m−1, M1=sm,u2 and M2=v2,tm covering Q2−F2. Note F0≤2n−2m<2n−5 for m≥3. By Lemma 2, there is a path R=u0,v0 covering Q0−F0. Let Pm=M1∪u2u0∪R∪v0v2∪M2.Case 2.Si=Ti for only one 0≤i≤2.Without loss of generality, letS0=T0. Then, S1≠T1, S2≠T2 and S1+S2=T1+T2. Without loss of generality, let S1>T1. Then, S2<T2 and S1−T1=T2−S2. Since VQi−F−S−T≥3n−1−2n−2m−2m≥m for 3≤m≤n, there are m cycles of length three Ci=wi0,wi1,wi2,wi0 for 1≤i≤m such that wij∈VQj−Fj−S−T for 0≤j≤2 .Case 2.1.S0=T0=0.Then,S1+S2=T1+T2=m.Case 2.1.1.S1=m and T1=0.Then,S2=0 and T2=m. Let S1=s1,…,sm, T2=t1,…,tm.Case 2.1.1.1.F0=0.LetS0′=si0:1≤i≤m−1, T0′=ti0:1≤i≤m−1. Then, S0′=T0′=m−1. By the induction hypothesis, there are m−1 disjoint paths Ri=si0,ti01≤i≤m−1 from S0′ to T0′ covering Q0−F0. Let Pi=sisi0∪Ri∪ti0ti1≤i≤m−1.LetW1=w11 and W2=w12. Note S1′=S1\sm=m−1=T2\tm=T2′ and F1+S1′≤2n−2m+m−1=2n−m−1≤2n−5 for m≥4. By Lemma 2, there is a path L=sm,w11 covering Q1−F1. Similarly, there is a path M=w12,tm covering Q2−F2. Let Pm=L∪w11w12∪M.Supposem=3. Then, F≤2n−2m=2n−6. Let W1=w11,w21 and W2=w12,w22. By Lemma 2, there are two paths L1=s1,w11 and L2=s2,w21 (resp. M1=w21,t1 and M2=w22,t2) covering Q1−F1 (resp. Q2−F2). Let Pi′=Li∪wi1wi2∪Mi for i=1,2. Then, s3,t3∈Pi′ for 1≤i≤2.Supposes3,t3∈P1′. Let P3=P1′s3,t3. Let u and v be the before and later vertex of s3 and t3, respectively. Let u0=Nu∩VQ0 and v0=Nv∩VQ0.Ifu0=v0, then let P1=P1′s1,u∪uu0,v0v∪P1′v,t1. Let wz∈P2′, w0=Nw∩VQ0 and z0=Nz∩VQ0. Note F0∪u0=1≤2n−5 for n≥3. By Lemma 2, there is a path R=w0,z0 covering Q0−F0−u0. Let P2=P2′−wz∪ww0,zz0∪R.Supposeu0≠v0. Note F0=0. By Lemma 1, there is a Hamilton path R=u0,v0 in Q0. Let P1=P1′s1,u∪uu0,vv0∪R∪P1′v,t1 and P2=P2′.Supposes3∈P1′ and t3∈P2′. Let u and v be the before and later vertex of s3 and t3 in P1′ and P2′, respectively. Let u0=Nu∩VQ0 and v0=Nv∩VQ0.Ifu0=v0, then let P1=P1′s1,u∪uu0,v0v∪P2′v,t2. Let wz∈L2, w0=Nw∩VQ0 and z0=Nz∩VQ0. Note F0∪u0=1≤2n−5 for n≥3. By Lemma 2, there is a path R=w0,z0 covering Q0−F0−u0. Let P2=P2′s2,t3−wz∪ww0,zz0∪R and P3=P1′s3,t1.Supposeu0≠v0. Note F0=0. By Lemma 1, there is a Hamilton path R=u0,v0 in Q0. Let P1=P1′s1,u∪uu0,vv0∪R∪P2′v,t2, P2=P2′s2,t3 and P3=P1′s3,t1.Case 2.1.1.2.F0=1.There is at most one vertexsi0∈F0 or ti0∈F0 for 1≤i≤m. Without loss of generality, let si0,ti0∉F0 for all 1≤i≤m−1. Let S0′=si0:1≤i≤m−2, T0′=ti0:1≤i≤m−2. Then, S0′=T0′=m−2. Note F0=1≤2n−1−2m−2. By the induction hypothesis, there are m−2 disjoint paths Ri=si0,ti01≤i≤m−2 from S0′ to T0′ covering Q0−F0. Let Pi=sisi0∪Ri∪ti0ti1≤i≤m−2.LetW1=w11,w21 and W2=w12,w22. Note S1′=S1\sm−1,sm=m−2=T2\tm−1,tm=T2′ and F1+S1′≤2n−2m−1+m−2=2n−m−3≤2n−6 for m≥3. By Lemma 3, there are two disjoint paths L1=sm−1,w11 and L2=sm,w21 covering Q1−F1. Similarly, there are two disjoint paths M1=w12,tm−1 and M2=w22,tm covering Q2−F2. Let Pm−1=L1∪w11w12∪M1 and Pm=L2∪w21w22∪M2.Case 2.1.1.3.F0≥2.Then,Fi≤2n−2m−2 for i=1,2. Let NQ1sm=u1,…,u2n−2 and ui0=Nui∩VQ0 for 1≤i≤2n−2. Since NQ1sm−S\sm=2n−2−m−1>2n−2m≥F for m≥3, there is an edge uiui01≤i≤2n−2 such that ui∈VQ1−F1−S1 and ui0∈VQ0−F0. Without loss of generality, let u1u10 be satisfied. Let NQ2tm=v1,…,v2n−2 and vi0=Nvi∩VQ0 for 1≤i≤2n−2. Since NQ2tm−T\tm=2n−2−m−1>2n−2m+1≥F+u10 for m≥3, there is an edge vivi0 such that vi∈VQ2−F2−T2 and vi0∈VQ0−F0−u10. Without loss of generality, let v1v10 be satisfied. Let S1′=S1\sm and T2′=T2\tm. Then, S1′=T2′=m−1. Let W1=wi1:1≤i≤m−1 and W2=wi2:1≤i≤m−1. Note F1∪sm,u1≤2n−2m and F2∪tm,v1≤2n−2m. By the induction hypothesis, there are m−1 disjoint paths Li=si,wi1 (resp. Mi=wi2,ti) 1≤i≤m−1 from S1′ to W1 (resp. from W2 to T2′) covering Q1−F1−sm−u1 (resp. Q2−F2−tm−v1). Note F0≤2n−2m<2n−5 for m≥3. By Lemma 2, there is a path R=u10,v10 covering Q0−F0. Let Pi=Li∪wi1wi2∪Mi1≤i≤m−1 and Pm=smu1,u1u10,tmv1,v1v10∪R.Case 2.1.2.S1=m and 1≤T1≤m−1.LetS1=s1,…,sm. Let T1=p≤m−1. Then, T2=m−p≤m−1. Let T1=t1,…,tp and T2=tp+1,…,tm. Let W2=wi2:p+1≤i≤m. Note W2=T2=m−p≤m−1. By the induction hypothesis, there are m−p disjoint paths Mi=wi2,tip+1≤i≤m covering Q2−F2.Case 2.1.2.1.F0=0.LetW1=wi1:p+1≤i≤m−1 for p≤m−2, W1=∅ for p=m−1. Then, W1=m−p−1. Note T1+W1=p+m−p−1=m−1=S1\sm. By the induction hypothesis, there are m−1 disjoint paths Li=si,ti1≤i≤p and Li=si,wi1p+1≤i≤m−1 covering Q1−F1. Let Pi′=Li1≤i≤p, Pi′=Li∪wi1wi2∪Mip+1≤i≤m−1. Then, sm∈VPj′ for some 1≤j≤m−1. We get Pj′=Pj′sj,sm∪Pj′sm,tj. Let u and v be the before and later vertex of sm in Pj′, respectively. Let u0=Nu∩VQ0, v0=Nv∩VQ0. Let W0=wm0.Supposewm0≠u0 and wm0≠v0. Note F0=0. By Lemma 3, there are two disjoint paths R1=u0,v0 and R2=sm0,wm0 covering Q0−F0. Let Pj=Pj′−sm∪uu0,vv0∪R1, Pi=Pi′i∈1,…,m−1\j and Pm=smsm0,wm2wm0∪R2∪Mm.Supposewm0=u0. Let z be the before vertex of u in Pj′ and z0=Nz∩VQ0. Note F0∪u0=1≤2n−5 for n≥3. By Lemma 2, there is a path R=z0,v0 covering Q0−F0−u0. Let Pj=Pj′sj,z∪zz0,vv0∪R∪Pj′v,tj, Pi=Pi′i∈1,…,m−1\j and Pm=smu,uu0,wm0wm2∪Mm. Similar to wm0=v0.Case 2.1.2.2.F0=1.Then,Fi≤2n−2m−1 for i=1,2. Since S1=m>1=F0, there is a vertex si∈S1 such that si0∉F0 for 1≤i≤m. Without loss of generality, let sm0∉F0. Let W1=wi1:p+1≤i≤m−1 for p≤m−2, W1=∅ for p=m−1. Then, W1=m−p−1. Note T1+W1=p+m−p−1=m−1=S1\sm and F1∪sm≤2n−2m. By the induction hypothesis, there are m−1 disjoint paths Li=si,ti1≤i≤p and Li=si,wi1p+1≤i≤m−1 covering Q1−F1−sm. Let Pi=Li1≤i≤p and Pi=Li∪wi1wi2∪Mi for p+1≤i≤m−1.LetW0=wm0. Note F0=1≤2n−5 for n≥3. By Lemma 2, there is a path R=sm0,wm0 covering Q0−F0. Let Pm=smsm0∪R∪wm0wm2∪Mm.Case 2.1.2.3.F0≥2.Then,Fi≤2n−2m−2 for i=1,2. Let NQ1sm=u1,…,u2n−2 and ui0=Nui∩VQ0 for 1≤i≤2n−2. Since NQ1sm−S\sm=2n−2−m−1>2n−2m+1≥F∪wm0 for m≥3, there is an edge uiui01≤i≤2n−2 such that ui∈VQ1−F1−S1 and ui0∈VQ0−F0−wm0. Without loss of generality, let u1u10 be satisfied.LetW1=wi1:p+1≤i≤m−1 for p≤m−2, W1=∅ for p=m−1. Then, W1=m−p−1. Note T1+W1=p+m−p−1=m−1=S1\sm and F1∪sm,u1≤2n−2m. By the induction hypothesis, there are m−1 disjoint paths Li=si,ti1≤i≤p and Li=si,wi1p+1≤i≤m−1 covering Q1−F1−sm−u1. Let Pi=Li1≤i≤p and Pi=Li∪wi1wi2∪Mip+1≤i≤m−1.LetW0=wm0. Note F0≤2n−2m<2n−5 for m≥3. By Lemma 2, there is a path R=u10,wm0 covering Q0−F0. Let Pm=smu1,u1u10∪R∪wm0wm2∪Mm.Case 2.1.3.1≤S1≤m−1.LetS1=p. Then, S2=m−p. Let S1=s1,…,sp and S2=sp+1,…,sm. If T1=m or T2=m, then it is similar to Case 2.1.2. Thus, 1≤Ti≤m−1 for i=1,2. Let 1≤T1=q<p=S1≤m−1. Then, 1≤T2=m−q≤m−1. Let T1=t1,…,tq and T2=tq+1,…,tm.LetWj=wij:q+1≤i≤p−1 for p−q≥2 and Wj=∅ for p−q=1 where j=1,2. Then, W1=W2=p−q−1≤m−3. Since VQi−F−S−T−Wi≥3n−1−2n−2m−2m−m−3≥3 for 3≤m≤n, there are two edges u0u1, v0v2 such that ui,vi⊂VQi−F−S−T−Wi for 0≤i≤2. Note F0=2n−2m<2n−5 for m≥3. By Lemma 2, there is a path R=u0,v0 covering Q0−F0.NoteW2+v2+S2=p−q−1+1+m−p=m−q=T2. By the induction hypothesis, there are m−q disjoint paths Mi=wi2,tiq+1≤i≤p−1, Mp=v2,tp and Mi=si,tip+1≤i≤m from S2∪W2∪v2 to T2 covering Q2−F2.NoteS1=p=q+p−q−1+1=T1+W1+u1. By the induction hypothesis, there are p disjoint paths Li=si,ti1≤i≤q, Li=si,wi1q+1≤i≤p−1, Lp=sp,u1 from S1 to T1∪W1∪u1 covering Q1−F1.LetPi=Li1≤i≤q, Pi=Li∪wi1wi2∪Miq+1≤i≤p−1, Pp=Lp∪u1u0∪R∪v0v2∪Mp and Pi=Mip+1≤i≤m.Case 2.2.1≤S0=T0≤m−1.By the induction hypothesis, there areS0 disjoint paths from S0 to T0 covering Q0−F0. Then, 1≤S1−T1=x=T2−S2≤m−1. Let Wj=wij:1≤i≤x for j=1,2. Then, T1+W1=S1≤m−1 and S2+W2=T2≤m−1. By the induction hypothesis, there are S1 (resp. T2) disjoint paths from S1 to T1∪W1 (resp. S2∪W2 to T2) covering Q1−F1 (resp. Q2−F2).Case 3.Si≠Ti for all 0≤i≤2.By Case 2, there arem cycles of length three Ci=wi0,wi1,wi2,wi0 for 1≤i≤m such that wij∈VQj−Fj−S−T for 0≤j≤2 .Case 3.1.Si>Ti for only one 0≤i≤2.Without loss of generality, letS0>T0. Then, S1<T1, S2<T2. We get 1≤S0−T0=T1−S1+T2−S2≤m.Case 3.1.1.S0=m and T0=0.Then,S1=S2=0 and 1≤T1,T2≤m−1. Let T1=p and T2=m−p. Let S0=s1,…,sm, T1=t1,…,tpand T2=tp+1,…,tm. Without loss of generality, let T1=p≥m−p=T2. Then, 2p≥m≥3. We get p≥2 and m−p≤m−2. Let W2=wi1:p+1≤i≤m. By the induction hypothesis, there are m−p disjoint paths Mi=wi2,tip+1≤i≤m from W2 to T2 covering Q2−F2.Case 3.1.1.1.F0=2n−2m.LetS0′=S0\s1. Then, S0′=m−1. Let W0=wi0:2≤i≤m. Note W0=m−1=S0′. By the induction hypothesis, there are m−1 disjoint paths Ri=si,wi2≤i≤m from S0′ to W0 covering Q0−F0. Then, s1∈Ri for some 2≤i≤m. Without loss of generality, let s1∈R2. Let u be the before vertex of s1 in R2 and u1=Nu∩VQ1.Supposeu1∈T1. Without loss of generality, let u1=t1. Let W1=wi1:2≤i≤p. Note W1=p−1=T1\t1 and F1∪t1=1≤2n−1−2m−2≤2n−1−2p−1. By the induction hypothesis, there are p−1 disjoint paths Li=wi1,ti2≤i≤p covering Q1−F1−t1. Let P1=R2s1,w20∪w20w21∪L2, P2=R2s2,u∪ut1, Pi=Ri∪wi0wi1∪Li3≤i≤p and Pi=Ri∪wi0wi2∪Mip+1≤i≤m.Supposeu1∉T1. Note W1∪u1=T1=p. By the induction hypothesis, there are p disjoint paths L1=u1,t1, Li=wi1,ti2≤i≤p from W1∪u1 to T1 covering Q1−F1. Let P1=R2s1,w20∪w20w21∪L2, P2=R2s2,u∪uu1∪L1, Pi=Ri∪wi0wi1∪Li3≤i≤p and Pi=Ri∪wi0wi2∪Mip+1≤i≤m.Case 3.1.1.2.F0=2n−2m−1.Then,F1∪F2≤1. Since S0=m>1≥F1, there is a vertex si such that si1∉F1 for 1≤i≤m. Without loss of generality, let s11∉F1. Let W0=wi0:2≤i≤m. Note S0\s1=m−1=W0 and F0∪s1=2n−2m. By the induction hypothesis, there are m−1 disjoint paths Ri=si,wi2≤i≤m from S0\s1 to W0 covering Q0−F0−s1. Let Pi=Ri∪wi0wi2∪Mip+1≤i≤m.LetW1=wi1:2≤i≤p. Note W1+s11=p=T1. By the induction hypothesis, there are p disjoint paths L1=s11,t1, Li=wi1,ti2≤i≤p from s11∪W1 to T1 covering Q1−F1. Let P1=s1s11∪L1 and Pi=Ri∪wi0wi1∪Li2≤i≤p.Case 3.1.1.3.F0≤2n−2m−2.Ifs11∉F, then it is similar to Case 3.1.1.2. Suppose s11∈F. Let NQ0s1=u1,…,u2n−2 and ui1=Nui∩VQ1 for 1≤i≤2n−2. Since NQ0s1−S\s1=2n−2−m−1>2n−2m−1+p≥F\s11+T1 for m>p, there is a vertex ui∈VQ0−F0−S such that ui1∈VQ1−F1−T1. Without loss of generality, let u1,u11 be satisfied.LetW0=wi0:2≤i≤m and u1∉W0. Then, F0∪s1,u1≤2n−2m. By the induction hypothesis, there are m−1 disjoint paths Ri=si,wi2≤i≤m from S0\s1 to W0 covering Q0−F0−s1−u1. Let Pi=Ri∪wi0wi2∪Mip+1≤i≤m.LetW1=wi1:2≤i≤p. Note W1+u11=p=T1. By the induction hypothesis, there are p disjoint paths L1=u11,t1, Li=wi1,ti2≤i≤p from u11∪W1 to T1 covering Q1−F1. Let P1=s1u1,u1u11∪L1 and Pi=Ri∪wi0wi1∪Li2≤i≤p.Case 3.1.2.S0=m and T0≥1.LetS0=s1,…,sm. Since Si<Ti for i=1,2, 1≤Ti≤m−2 for i=0,1,2. Let 1≤T0=m−p−q≤m−2, 1≤T1=p≤m−2 and 1≤T2=q≤m−2. Let T0=t1,…,tm−p−q, T1=tm−p−q+1,…,tm−q and T2=tm−q+1,…,tm.Case 3.1.2.1.F0=2n−2m.Then,F1=F2=0. Let S1′=si1:m−p−q+1≤i≤m−q and S2′=si2:m−q+1≤i≤m. Note S1′=p=T1 and S2′=q=T2. By the induction hypothesis, there are p (resp. q) disjoint paths Li=si1,tim−p−q+1≤i≤m−q (resp. Mi=si2,tim−q+1≤i≤m) from S1′ to T1 (resp. S2′ to T2 covering Q1−F1 (resp. Q2−F2 ). Let Pi=sisi1∪Lim−p−q+1≤i≤m−q and Pi=sisi2∪Mim−q+1≤i≤m.LetS0′=si:1≤i≤m−p−q. Note S0′=m−p−q=T0 and F0+S0\S0′=2n−2m+p+q≤2n−1−2m−p−q for p+q≥2. By the induction hypothesis, there are m−p−q disjoint paths Pi=si,ti1≤i≤m−p−q from S0′ to T0 covering Q0−F0.Case 3.1.2.2.F0=2n−2m−1.SinceF1∪F2≤1<m=S0, there is a vertex si such that si2∉F2 for 1≤i≤m. Without loss of generality, let sm2∉F2. Let W0=wi0:m−p−q+1≤i≤m−1 for p+q≥2. Note W0+T0=p+q−1+m−p−q=m−1=S0\sm and F0∪sm=2n−2m. By the induction hypothesis, there are m−1 disjoint paths Ri=si,ti1≤i≤m−p−q and Ri=si,wim−p−q+1≤i≤m−1 from S0′\sm to T0∪W0 covering Q0−F0−sm. Let Pi=Ri1≤i≤m−p−q.LetW1=wi1:m−p−q+1≤i≤m−q. Note T1=W1=p≤m−2 and F1≤1≤2n−1−2m−2≤2n−1−2p. By the induction hypothesis, there are p disjoint paths Li=wi1,tim−p−q+1≤i≤m−q from W1 to T1 covering Q1−F1. Let Pi=Ri∪wi0wi1∪Lim−p−q+1≤i≤m−q.LetW2=wi2:m−q+1≤i≤m−1 for q≥2 and W2=∅ for q=1. Since wi2∈VQ2−F−S−T, sm2∉W2. Note T2=W2∪sm2=q≤m−2 and F2≤1≤2n−1−2m−2≤2n−1−2q. By the induction hypothesis, there are q disjoint paths Mi=wi2,tim−q+1≤i≤m−1 and Mm=sm2,tm from W2∪sm2 to T2 covering Q2−F2. Let Pi=Ri∪wi0wi2∪Mim−q+1≤i≤m−1 and Pm=smsm2∪Mm.Case 3.1.2.3.F0≤2n−2m−2.LetNQ0sm=u1,…,u2n−2 and ui2=Nui∩VQ2 for 1≤i≤2n−2. Since NQ0sm−S\sm=2n−2−m−1>2n−2m+q≥F+T2 for m−1>q, there is a vertex ui∈VQ0−F0−T0 such that ui2∈VQ2−F2−T2. Without loss of generality, let u1 be satisfied.LetW0=wi0:m−p−q+1≤i≤m−1 and u1∉W0. Note S0′=S\sm=m−1=T0+W0 and F0∪sm,u1=2n−2m. By the induction hypothesis, there are m−1 disjoint paths Ri=si,ti1≤i≤m−p−q and Ri=si,wim−p−q+1≤i≤m−1 from S0′ to T0∪W0 covering Q0−F0−sm−u1. Let Pi=Ri1≤i≤m−p−q.LetW1=wi1:m−p−q+1≤i≤m−q. Note T1=W1=p≤m−2. By the induction hypothesis, there are p disjoint paths Li=wi1,tim−p−q+1≤i≤m−q from W1 to T1 covering Q1−F1. Let Pi=Ri∪wi0wi1∪Lim−p−q+1≤i≤m−q.LetW2=wi2:m−q+1≤i≤m−1 for q≥2 and W2=∅ for q=1. Note T2=W2∪u12=q≤m−2. By the induction hypothesis, there are q disjoint paths Mi=wi2,tim−q+1≤i≤m−1 and Mm=u12,tm from W2∪u12 to T2 covering Q2−F2. Let Pi=Ri∪wi0wi2∪Mim−q+1≤i≤m−1 and Pm=smu1,u1u12∪Mm.Case 3.1.3.1≤S0≤m−1.IfTi=m for some 1≤i≤2, then it is similar to Case 3.1.1 or 3.1.2. Since Ti>Si≥0 for 1≤i≤2, 1≤Ti≤m−1 for 1≤i≤2. Let W0=wi0:1≤i≤S0−T0, W1=wi1:1≤i≤T1−S1 and W2=wi2:1≤i≤T2−S2. Thus, W0=S0−T0=T1−S1+T2−S2=W1+W2. Note S0=T0+W0≤m−1, T1=S1+W1≤m−1 and T2=S2+W2≤m−1. By the induction hypothesis, there are S0, T1 and T2 disjoint paths from S0 to W0∪T0, from S1∪W1 to T1 and from S2∪W2 to T2 covering Q0−F0, Q1−F1 and Q2−F2, respectively.Case 3.2.Si>Ti for two 0≤i≤2.There is only onei such that Si<Ti for 0≤i≤2. It is similar to Case 3.1.


## 4. One-to-Many Disjoint Paths

Lemma 4.
Let0≤i≤2 be a 3-ary n-cube for n≥2. Let F be a faulty set of VQn3. Let s,t1,t2 be the subset of VQn3−F. If F≤2n−3, then there exist two disjoint paths from s to tii=1,2 covering Qn3−F.Proof.
NoteF≤2n−3 for n≥2. By Lemma 2, there is a path P=t1,t2 covering Qn3−F. Then, s∈VP. Thus, there are two disjoint paths P−1s,t1 and Ps,t2 covering Qn3−F.Lemma 5.
LetQn3 be a 3-ary n-cube for n≥3. Let F be a faulty set of VQn3. Let C=s0,s1,s2,s0 be a fault-free cycle of length three, s∈VC and T be the subset of VQn3−F−VC with T=3. If F≤2n−4, then there are three disjoint paths from s to T covering Qn3−F.Proof.
LetT=t0,t1,t2. We decompose Qn3 into three isomorphic subgraphs Q0,Q1,Q2 along one dimension such that si∈VQi for i∈0,1,2. Suppose there is sti∈EQn3 for some 0≤i≤2. Let Pi=s,ti. Note F∪ti≤2n−3. By Lemma 4, there are two disjoint paths Pj=s,tj for j∈0,1,2\i. Thus, the lemma holds. So, suppose sti∉EQn3 for all 0≤i≤2. Let Ti=T∩VQi and Fi=F∩VQi for 0≤i≤2. Without loss of generality, let T0>0 and s=s0.Case 1.T0=1, T1=2 and T2=0.LetT0=t0 and T1=t1,t2.Case 1.1.Fi≤2n−5 for 0≤i≤2.By Lemma2, there is a Hamilton path L=t1,t2 in Q1−F1. Since VL−2F≥3n−1−22n−4>0 for n≥3, there is an edge xy∈R such that xi,yi∈VQi−Fi for i=0,2 where xi=Nx∩VQi and yi=Ny∩VQi. By Lemma 2, there is a Hamilton path M=s2,y2 in Q2−F2. By Lemma 4, there are two disjoint paths R1=s,t0 and R2=s,x0 covering Q0−F0. Let P0=R1, P1=R2∪x0x∪L−1x,t1 and P2=ss2∪M∪y2y∪Ly,t2.Case 1.2.Fi=2n−4 for some 0≤i≤2.Case 1.2.1.F0=2n−4.Letf∈F0 and F0′=F0\f. By Lemma 4, there are two disjoint paths R1=s,t0 and R2=s,f covering Q0−F0. Let u be the before vertex of f in R2 and u1=Nu∩VQ1.u1=t1 or u1=t2. Without loss of generality, let u1=t1. Note F1∪t1=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path L=s1,t2 in Q1−F1−t1. Let xy∈L, x2=Nx∩VQ2 and y2=Ny∩VQ2. By Lemma 2, there is a Hamilton path M=x2,y2 in Q2−F2. Let P0=R1, P1=R2s,u∪ut1 and P2=ss1∪L−xy∪xx2,yy2∪M.u1≠t1 and u1≠t2. Let t22=Nt2∩VQ2. Note F1∪t2=1≤2n−5 and F2=0. By Lemma 2, there is a Hamilton path L=u1,t1 and M=s2,t22 in Q1−F1−t2 and Q2−F2, respectively. Let P0=R1, P1=R2s,u∪uu1∪L and P2=ss2∪M∪t22t2.Case 1.2.2.F1=2n−4.Letf∈F1 and F1′=F1\f. By Lemma 4, there are two disjoint paths L1=f,t1 and L2=f,t2 covering Q1−F1′. Let zi be the next vertex of f in Li for i=1,2 and zij=Nu∩VQj for j=0,2. By Lemma 4, there are two disjoint paths R1=s,t0 and R2=s,z10 covering Q0−F0. By Lemma 2, there is a Hamilton path M=s2,z22 in Q2−F2. Let P0=R1, P1=R2∪z10z1∪L1z1,t1 and P2=ss2∪M∪z22z2∪L2z2,t2.Case 1.2.3.F2=2n−4.By Lemma2, there is a Hamilton path R=s,t0 in Q0−F0. Let f∈F2 and F2′=F2\f. By Lemma 2, there is a Hamilton path M=s2,f in Q2−F2′. Let u be the before vertex of f in M and u1=Nu∩VQ1.u1=t1 or u1=t2. Without loss of generality, let u1=t1. Note F1∪t1=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path L=s1,t2 in Q1−F1−t1. Let P0=R, P1=ss2∪Ms2,u∪ut1 and P2=ss1∪L.u1≠t1 and u1≠t2. Since u≠s2, u1≠s1. By Lemma 3, there are two disjoint paths L1=u1,t1 and L2=s1,t2 covering Q1−F1. Let P0=R, P1=ss2∪Ms2,u∪uu1∪L1 and P2=ss1∪L.Case 2.T0=1, T1=1 and T2=1.LetT0=t0, T1=t1 and T2=t2.Case 2.1.Fi≤2n−5 for 0≤i≤2.By Lemma2, there is a Hamilton path R=s,t0, L=s1,t1 and M=s2,t2 in Q0−F0, Q1−F1 and Q2−F2, respectively. Let P0=R, P1=ss1∪L and P2=ss2∪M.Case 2.2.Fi=2n−4 for some 0≤i≤2.Case 2.2.1.F0=2n−4.Then,F1=F2=0. Since F0=2n−4≥2 for n≥3, let f∈F0 and F0′=F0\f. Then, F0′=2n−5. By Lemma 4, there are two disjoint paths P=s0,t0 and R=s0,f covering Q0−F0. Then, VR≥2.Case 2.2.1.1.VR=2.Then,R=s0,f. By Lemma 2, there is a Hamilton path Pi′=si,ti in Qi for i=1,2. Let P0=P, P1=ss1∪P1′ and P2=ss2∪P2′.Case 2.2.1.2.VR≥3.Letu be the before vertex of f in R. Let ui=Nu∩VQi for i∈1,2. By the definition of Qn3, ui∈VQi−si for i∈1,2.Case 2.2.1.2.1.u1=t1 or u2=t2.Without loss of generality, letu1=t1. Since VQi−Fi−si,t1,t2=3n−1−3>1 for i=1,2, there is an edge x1x2 such that xi∈VQi−Fi−si,t1,t2 for i=1,2. Note F1∪t1=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path L=s1,x1 in Q1−F1−t1. Note F2=0. By Lemma 2, there is a Hamilton path M=x2,t2 in Q2. Let P0=P, P1=Rs,u∪ut1, and P2=ss1∪L∪x1x2∪M.Case 2.2.1.2.2.u1≠t1 and u2≠t2.By Lemma2, there is a Hamilton path L=u1,t1 and M=s2,t2 in Q1 and Q2, respectively. Let P0=P, P1=Rs,u∪uu1∪L, P1=ss2∪M.Case 2.2.2.F1=2n−4 or F2=2n−4.LetF1=2n−4. Then, F0=F2=0. Note F1=2n−4≥2 for n≥3. Let f∈F1. Then, F1\f=2n−5. By Lemma 4, there are two disjoint paths L1=s1,t1 and L2=s1,f covering Q1−F1−f.Case 2.2.2.1.VL2=2.Then,L2=s1,f. By Lemma 2, there is a Hamilton path R=s,t0 and M=s2,t2 in Q0 and Q2, respectively. Let P0=R, P1=ss1∪L1 and P2=ss2∪M.Case 2.2.2.2.VL2=3.LetL2=s1,u,f. Let u2=Nu∩VQ2. Let w be the later vertex of s1 in L1 and wi=Nw∩VQi for i=0,2.Supposeu2=t2. Note F2∪t2=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path M=s2,w2 in Q2−F2−t2. By Lemma 2, there is a Hamilton path R=s,t0 in Q0. Let P0=R, P1=ss2∪M∪w2w∪L1w,t1 and P2=s,s1,u,t2.Supposeu2≠t2. By Lemma 2, there is a Hamilton path M=u2,t2 in Q2. By the definition of Qn3, w0∈Ns. Since sti∉EQn3, w0≠t0. By Lemma 4, there are two disjoint paths R1=s,t0 and R2=s,w0 covering Q0−F0. Let P0=R1, P1=R2∪w0w∪L1w,t1 and P2=s,s1,u,u2∪M.Case 2.2.2.3.VL2≥4.By Lemma2, there is a Hamilton path R=s,t0 in Q0. Let u and v be the later and before vertex of s1 and f in L2, respectively. Let u2=Nu∩VQ2 and v2=Nv∩VQ2.Supposet2=u2 or t2=v2. Without loss of generality, let t2=u2. Note F2∪t2=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path M=s2,v2 in Q2−F2−t2. Let P0=R, P1=ss1∪L1 and P2=ss2∪M∪v2v∪L2−1v,u∪ut2.Supposet2≠u2 and t2≠v2. By Lemma 3, there are two disjoint paths M1=s2,u2 and M2=v2,t2 covering Q2−F2. Let P0=R, P1=ss1∪L1 and P2=ss2∪M1∪u2u∪L2u,v∪vv2∪M2.Case 3.T0=2, T1=1 and T2=0.LetT0=t0,t1 and T1=t2.Case 3.1.Fi≤2n−6 for all 0≤i≤2.SinceVQi−F−T−s≥3n−1−2n−4−3−1>1 for n≥3, there is an edge x0x2 such that xi∈VQi−Fi−Ti−si for i=0,2. By Lemma 2, there are two disjoint paths R1=s,t0 and R2=x0,t1 covering Q0−F0. By Lemma 3, there is a Hamilton path L=s1,t2 and M=s2,x2 in Q1−F1 and Q2−F2, respectively. Let P0=R1, P1=ss2∪M∪x2x0∪R2 and P2=ss1∪L.Case 3.2.Fi=2n−5 for some 0≤i≤2.We getFj≤1≤2n−5 for n≥3 and j∈0,1,2\i. By Lemma 4, there are two disjoint paths R1=s,t0 and R2=s,t1 covering Q0−F0. Let P0=R1, P1=R2.SinceVQi−F−T−si≥3n−1−2n−4−3−1>1, there is an edge x1x2 such that xi∈VQi−Fi−Ti−si for i=1,2. Note Fi≤2n−5 for i=1,2. By Lemma 2, there is a Hamilton path L=x1,t2 and M=s2,x2 in Q1−F1 and Q2−F2, respectively. Let P2=ss2∪M∪x2x1∪L.Case 3.3.Fi=2n−4 for some 0≤i≤2.Case 3.3.1.F0=2n−4.Then,F1=F2=0. By Lemma 2, there is a Hamilton path L=s1,t2 in Q1. Let P2=ss1∪L. Note F0=2n−4≥2 for n≥3. Let f∈F0. Then, F0′=F0\f=2n−5. By Lemma 4, there are two disjoint paths P=s,t0 and R=s,t2 covering Q0−F0′. Without loss of generality, let f∈VR. Then, VR≥3.Case 3.3.1.1.sf∈ER and ft1∈ER.Then,R=s0,f,t1. Let t12=Nt1∩VQ2. Note that F2=0. By Lemma 2, there is a Hamilton path M=s2,t12 in Q2. Let P0=P and P1=ss2∪M∪t12t1.Case 3.3.1.2.sf∈ER and ft1∉ER.Letu be the later vertex of f in R and u2=Nu∩VQ2. Note that F2=0. By Lemma 2, there is a Hamilton path M=s2,u2 in Q2. Let P0=P and P1=ss2∪M∪u2u∪Ru,t1.Case 3.3.1.3.sf∉ER and ft1∈ER.Letw and u be the later and before vertex of s0 and f in P and R, respectively. Let u2=Nu∩VQ2, w2=Nw∩VQ2 and t12=Nt1∩VQ2. By the definition of Qn3, u2,w2,t12 are different in VQ2−s2. Note that F2=0≤2n−6 for n≥3. By Lemma 3, there are two disjoint paths M1=s2,t12 and M2=u2,w2 covering Q2−F2. Let P0=Rs,u∪uu2∪M2∪w2w∪Pw,t0 and P1=ss2∪M1∪t12t1.Case 3.3.1.4.sf∉ER and ft2∉ER.Letu and v be the before and later vertex of f in R, respectively. Let w be the later vertex of s0 in P. Let u2=Nu∩VQ2, v2=Nv∩VQ2 and w2=Nw∩VQ2. By the definition of Qn3, u2,v2,w2 are different in VQ2−s2. Note that F2=0≤2n−6 for n≥3. By Lemma 3, there are two disjoint paths M1=s2,v2 and M2=u2,w2 covering Q2−F2. Let P0=Rs,u∪uu2∪M2∪w2w∪Pw,t0 and P1=ss2∪M1∪v2v∪Rv,t1.Case 3.3.2.F1=2n−4.NoteF1=2n−4≥2 for n≥3. Let f∈F1. Then, F1′=F1\f=2n−5. By Lemma 4, there are two disjoint paths L1=s1,t2 and L2=s1,f covering Q1−F1′. Let P2=ss1∪L1. Then, VL2≥2.Case 3.3.2.1.VL2=2.Then,L2=s1,f. Let t12=Nt1∩VQ2. Note F0∪t1=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path R=s,t0 in Q0−F0−t1. Note F2=0. By Lemma 2, there is a Hamilton path M=s2,t12 in Q2. Let P0=R and P1=ss2∪M∪t12t1.Case 3.3.2.2.VL2=3.LetL2=s1,u,f, ui=Nu∩VQi for i=0,2. Then, ui∈VQi−si for i=0,2.Supposeu0=t0 or u0=t1. Without loss of generality, let u0=t1. Note F0∪t1=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path R=s,t0 in Q0−F0−t1. Note F2=0. By Lemma 2, there is a Hamilton path M=s2,u2 in Q2. Let P0=R and P1=ss2∪M∪u2u,ut1.Supposeu0≠t0 and u0≠t1. Note F0=0≤2n−6 for n≥3. By Lemma 3, there are two disjoint paths R1=s,t0 and R2=u0,t1 covering Q0−F0. Note F2=0. By Lemma 2, there is a Hamilton path M=s2,u2 in Q2. Let P0=R1 and P1=ss2∪M∪u2u,uu0∪R2.Case 3.3.2.3.VL2≥4.Letu and v be the later and before vertex of s1 and f in L2, respectively. Let u2=Nu∩VQ2 and v0=Nv∩VQ0. Note F2=0. By Lemma 2, there is a Hamilton path M=s2,u2 in Q2.Supposev0=t0 or v0=t1. Without loss of generality, let v0=t1. Note F0∪t1=1≤2n−5 for n≥3. By Lemma 3, there is a Hamilton path R=s,t0 in Q0−F0−t1. Let P0=R and P1=ss2∪M∪u2u∪L2u,v∪vt1.Supposev0≠t0 and v0≠t1. Note F0=0≤2n−6 for n≥3. By Lemma 2, there are two disjoint paths R1=s,t0 and R2=v0,t1 covering Q0−F0. Let P0=R1 and P1=ss1∪M∪u2u∪L2u,v∪vv0∪R2.Case 3.3.3.F2=2n−4.NoteF1=0. By Lemma 2, there is a Hamilton path L=s1,t2 in Q1. Let P2=ss1∪L. Note F2=2n−4≥2 for n≥3. Let f∈F2. Then, F2′=F2\f=2n−5. By Lemma 2, there is a Hamilton path M=s2,f in Q2−F2′. Let w be the before vertex of f in M. Let w0=Nw∩VQ0. Then, w0∈VQ0−s0.Case 3.3.3.1.w0=t0 or w0=t1.Without loss of generality, letw0=t1. Note F0∪t1=1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path R=s,t0 in Q0−F0−t1. Let P0=R and P1=ss2∪Ms2,w∪wt1.Case 3.3.3.2.w0≠t0 and w0≠t1.NoteF0=0≤2n−6 for n≥3. By Lemma 3, there are two disjoint paths R1=s,t0 and R2=w0,t1 covering Q0−F0. Let P0=R1 and P1=ss2∪Ms2,w∪ww0∪R2.Case 4.T0=3, T1=0 and T2=0.LetT0=t0,t1,t2. Since VQi−F−T−s≥3n−1−2n−4−3−1>2 for n≥3, there are two cycles of length three Ci=wi0,wi1,wi2,wi0 such that wij∈VQj−Fj−Tj−sj for 0≤j≤2 and i∈1,2.Case 4.1.Fi≤2n−6 for all 0≤i≤2.Lettij=Nti∩VQj for 0≤i≤2 and j∈1,2. Suppose Fi≤2 for i∈1,2. There is ti1∈VQ1−F1 for 0≤i≤2. Let t2 be satisfied. By Lemma 2, there is a Hamilton path L=w11,t21 and M=s2,w12 in Q1−F1 and Q2−F2, respectively. Note F0∪t2≤2n−5. By Lemma 4, there are two disjoint paths R1=s,t0 and R2=s,t1 covering Q0−F0. Let P0=R1, P1=R2 and P2=ss2∪M∪w12w11∪L∪t21t2.SupposeFi≥3 for i∈1,2. Then, F0≤2n−4−6=2n−10. By Theorem 1, there are three disjoint paths R0=s,t0 and Ri=wi0,tii=1,2 covering Q0−F0. By Lemma 2, there is a Hamilton path L=s1,w11 and M=s2,w22 in Q1−F1 and Q2−F2, respectively. Let P0=R0, P1=ss1∪L∪w11w10∪R1 and P2=ss2∪M∪w22w20∪R2.Case 4.2.Fi=2n−5 for some 0≤i≤2.Case 4.2.1.F0=2n−5.Then,F1∪F2≤1. Without loss of generality, let F1=0 and F2≤1. By Lemma 4, there are two disjoint paths R0=s,t0 and R1=s,t1 covering Q0−F0. Then, t2∈Ri for some 0≤i≤1. Without loss of generality, let t2∈R1. Then, R1=R1s,t2∪R1t2,t1. Let z and u be the later vertex of s and t2 in R0 and R1, respectively. Let ui=Nu∩VQi and zi=Nz∩VQi for 1≤i≤2.Supposeu2∈F2. Then, z2∉F2. By Lemma 2, there is a Hamilton path L=s1,u1 and M=s2,z2 in Q1−F1 and Q2−F2, respectively. Let P0=ss2∪M∪z2z∪R0z,t0, P1=ss1∪L∪u1u∪R1u,t1 and P2=R0s,t2.Supposeu2∉F2. By Lemma 2, there is a Hamilton path L=s1,z1 and M=s2,u2 in Q1−F1 and Q2−F2, respectively. Let P0=ss1∪L∪z1z∪R0z,t0, P1=ss2∪M∪u2u∪R1u,t1 and P2=R0s,t2.Case 4.2.2.F1=2n−5 or F2=2n−5.LetF1=2n−5. Then, F0∪F2≤1.Case 4.2.2.1.F0=0.SinceF2≤1, there is a vertex ti such that ti2∉F2 where ti2=Nti∩VQ2 for 0≤i≤2. Let t2 be satisfied. By Lemma 2, there is a Hamilton path L=s1,w11 and M=w12,t22 in Q1−F1 and Q2−F2, respectively. Note F0∪t2=1≤2n−5. By Lemma 4, there are two disjoint paths R0=s,t0 and R1=s0,t1 covering Q0−F0. Let P0=R0, P1=R1 and P2=ss1∪L∪w11w12∪M∪t22t2.Case 4.2.2.2.F2=0.Then,F0≤1≤2n−5 for n≥3. By Lemma 4, there are two disjoint paths R1=s0,t1 and R2=s0,t2 covering Q0−F0. Then, t0∈Ri for some 1≤i≤2. Without loss of generality, let t0∈R1. Then, R1=R1s0,t0∪R1t0,t1. Let u and v be the later vertex of t0 and s0 in R1 and R2, respectively. Let u2=Nu∩VQ2 and v2=Nv∩VQ2. Since VQi−F−si,ui,vi≥3n−1−2n−4−3≥1 for n≥3, there is an edge z1z2 such that zi∈VQi−F−si,u2,v2 for 1≤i≤2.NoteF1=2n−5. By Lemma 2, there is a Hamilton path L=s1,z1 in Q1−F1. Note F2=0≤2n−6 for n≥3. By Lemma 3, there are two disjoint paths M1=z2,u2 and M2=s2,v2 covering Q2−F2. Let P0=R1s0,t0, P1=ss1∪L∪z1z2∪M1∪u2u∪R1u,t1 and P2=ss2∪M2∪v2v∪R2v,t2.Case 4.3.Fi=2n−4 for some 0≤i≤2.Case 4.3.1.F0=2n−4.Then,F1=F2=0. Note F0=2n−4≥2 for n≥3. Let f1,f2∈F0. Let F0′=F0\f1,f2∪t2. Then, F0′=2n−5. By Lemma 4, there are two disjoint paths R0=s,t0 and R1=s,t1 covering Q0−F0′. Then, f1,f2∈Ri for 0≤i≤1. Let f1,f2∈R1. Let u and v be the before and later vertex of f1, ui=Nu∩VQi and vi=Nv∩VQi for 1≤i≤2. Let x and y be the before and later vertex of f2, xi=Nx∩VQi and yi=Ny∩VQi for 1≤i≤2. Note F1=F2=0. By Lemma 2, there is a Hamilton path L=u1,v1 in Q1−F1. Let t22=Nt2∩VQ2. By Lemma 3, there are two disjoint paths M1=x2,y2 and M2=s2,t22 covering Q2−F2. Let P0=R0, P1=R1−f1,f2∪L∪M and P2=ss2∪M2∪t22t2. Similarly, f1∈R0 and f2∈R1.Case 4.3.2.F1=2n−4 or F2=2n−4.LetF1=2n−4. Then, F0=F2=0. Note F1=2n−4≥2 for n≥3. Let f∈F1. Then, F1′=F1\f=2n−5. By Lemma 2, there is a Hamilton path L=s1,f in Q1−F1. Let u be the before vertex of f in L and u2=Nu∩VQ2. Since T=3<1, there is a ti such that ti2≠u2 where ti2=Nti∩VQ2 for 0≤i≤2. Let t2 be satisfied. Note F0∪t2=1≤2n−5. By Lemma 4, there are two disjoint paths R0=s,t0 and R1=s,t1 covering Q0−F0−t2. By Lemma 2, there is a Hamilton path M=u2,t22 in Q2−F2. Let P0=R0, P1=R1 and P2=ss1∪L−f∪uu2∪M∪t22t2.Theorem 2.
LetQn3 be a 3-ary n-cube for n≥2. Let F be a vertex faulty set of Qn3. Let C be a fault-free cycle of length three. Let s∈VC and T⊂VQn3−F−VC with 2≤T=m≤n. If F≤2n−m−1, then there are m disjoint paths from s to T covering Qn3−F.Proof.
We prove the theorem by induction onm. If m=2, then T=2 and F≤2n−3. By Lemma 4, there are two disjoint paths from s to T covering Qn3−F. If m=3, then T=3 and F≤2n−4. By Lemma 5, there are three disjoint paths from s to T covering Qn3−F.
Assume the theorem is true form−1. Now we prove the theorem holds on m for 4≤m≤n. Let T=t1,…,tm. Suppose there is sti∈EQn3 for some 1≤i≤m. Then, T\ti=m−1 and F∪ti≤2n−m=2n−m−1−1. By the induction hypothesis, there are m−1 disjoint paths Pj=s,tjj∈1,…,m\i covering Qn3−F−ti. Let Pi=s,ti. Thus, P1,…,Pm are m disjoint paths covering Qn3−F. So, we suppose sti∉EQn3 for all 1≤i≤m.
LetC=s0,s1,s2,s0. So, we can decompose Qn3 into three subgraphs Q0,Q1,Q2 along one dimension such that si∈VQi0≤i≤2. Let Ti=T∩VQi and Fi=F∩VQi for 0≤i≤2. Without loss of generality, let T0≥1 and s=s0.Case 1.T0=m.LetT0=t1,…,tm and tij=Nti∩VQj for 1≤i≤m and j=1,2. Then, T1=T2=0.Case 1.1.2n−m−2≤F0≤2n−m−1.Then,F1∪F2≤1. Without loss of generality, let F1=0 and F2≤1. Let T0′=T0\tm−1,tm. Then, T0′=m−2. Note F0≤2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤m−2 covering Q0−F0. Then, tm−1,tm∈∪i=1m−2VRi−ti−s.Case 1.1.1.tm−1,tm∈VRi for some 1≤i≤m−2.Without loss of generality, lettm−1,tm∈VR1. Let tm−1 is before tm in R1. Then, R1=R1s,tm−1∪R1tm−1,tm∪R1tm,t1. Let u and v be the later vertex of tm−1 and tm on R1, respectively. Let ui=Nu∩VQivi=Nv∩VQi for i=1,2. Since F2≤1, u2∉F2 or v2∉F2.Supposeu2∉F2. Note F2≤1≤2n−5 for n≥3. By Lemma 2, there is a Hamilton path M=s2,u2 in Q2−F2. Note F1=0. By Lemma 2, there is a Hamilton path L=s1,v1 in Q1. Let P1=ss1∪L∪v1v∪R1v,t1, Pi=Ri2≤i≤m−2, Pm−1=R1s,tm−1 and Pm=ss2∪M∪u2u∪R1u,tm. Similar to v2∉F2.Similarly,tm is before tm−1 on R1.Case 1.1.2.tm−1∈VRi, tm∈VRj for 1≤i,j≤m−2 and i≠j.Without loss of generality, lettm−1∈VR1 and tm∈VR2. Then, R1=R1s,tm−1∪R1tm−1,t1 and R2=R2s,tm∪R2tm,t2. Let u and v be the later vertex of tm−1 and tm on R1 and R2, respectively. Let ui=Nu∩VQi and vi=Nv∩VQi for i=1,2. Since F2≤1, u2∉F2 or v2∉F2.Supposeu2∉F2. By Lemma 2, there is a Hamilton path L=s1,v1 and M=s2,u2 in Q1−F1 and Q2−F2, respectively. Let P1=ss2∪M∪u2u∪R1u,t1, P2=ss1∪L∪v1v∪R2v,t2, Pi=Ri3≤i≤m−2, Pm−1=R1s,tm−1 and Pm=R2s,tm. Similar to v2∉F2.Case 1.2.F0=2n−m−3.Then,F1∪F2≤2. Without loss of generality, let F1≤1. Since T0=m>1≥F1, there is a vertex ti such that ti1∉F1 for 1≤i≤m. Without loss of generality, let tm1∉F1. Note F0∪tm=2n−m−2=2n−1−m−1−1. By the induction hypothesis, there are m−1 disjoint paths Pi=s,ti1≤i≤m−1 covering Q0−F0−tm.SinceVQi−F−si,tmi≥3n−1−2n−m−1−2≥5 for n≥3, there is an edge w1w2 such that wi∈VQi−F−si,tmi for i=1,2. Note F1∪F2≤2≤2n−5 for n≥m≥4. By Lemma 2, there is a Hamilton path R=w1,tm1 and L=s2,w2 in Q1−F1 and Q2−F2, respectively. Let Pm=ss2∪L∪w2w1∪R∪tm1tm.Case 1.3.F0≤2n−m−4.Iftm1∉F1, then it is similar to Case 1.2. Suppose tm1∈F1. Let T0′=T\tm. Let NQ0tm=u1,…,u2n−2. Since NQ0tm−T0′=2n−2−m−1=2n−m−1>2n−m−2≥F\tm1, there is a vertex ui∈VQ0−F0−T0−s such that uij∉Fj\tmj where uij=Nui∩VQj for 1≤j≤2 and 1≤i≤2n−2. Without loss of generality, let u1 be satisfied. Note F0+tm,u1≤2n−m−2=2n−1−m−1−1. By the induction hypothesis, there are m−1 disjoint paths Pi=s,ti1≤i≤m−1 covering Q0−F0−tm,u1. Since VQi−F−si,tmi,u1i≥3n−1−2n−m−1−3>1 for 4≤m≤n, there is an edge x1x2 such that xi∈VQi−Fi−si,tmi,u1i for i=1,2. Note Fi≤2n−5 for i=1,2. By Lemma 2, there is a Hamilton path L=x1,u11 and M=s2,x2 in Q1−F1 and Q2−F2, respectively. Let Pm=ss2∪M∪x2x1∪L∪u11u1,u1tm.Case 2.T0=m−1.LetT0=t1,…,tm−1, T1=tm and T2=0.Case 2.1.F0=2n−m−1.Then,F1=F2=0. Let T0′=T0\tm−1. Then, T0′=m−2. Note F0=2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤m−2 covering Q0−F0. Then, tm−1∈VRi−ti−s for some 1≤i≤m−2. Without loss of generality, let tm−1∈R1. Let u be the later vertex of tm on R1 and u2=Nu∩VQ2. By Lemma 2, there is a Hamilton path L=s1,tm and M=s2,u2 in Q1 and Q2, respectively. Let P1=ss2∪M∪u2u∪R1u,t1, Pi=Ri2≤i≤m−2, Pm−1=R1s,tm−1 and Pm=ss1∪L.Case 2.2.F0≤2n−m−2.NoteF0≤2n−m−2=2n−1−m−1−1. By the induction hypothesis, there are m−1 disjoint paths Pi=s,ti1≤i≤m−1 covering Q0−F0. Since VQi−F−si,tm≥3n−1−2n−m−1−2>1 for 4≤m≤n, there is an edge x1x2 such that xi∈VQi−Fi−si,tm for i=1,2. Note Fi≤2n−5 for i=1,2. By Lemma 2, there is a Hamilton path L=x1,tm and M=s2,x2 in Q1−F1 and Q2−F2, respectively. Let Pm=ss2∪M∪x2x1∪L.Case 3.1≤T0≤m−2.LetT0=p. Then, 1≤p≤m−2 and 2≤T1∪T2=m−p≤m−1.Case 3.1.T1=0 or T2=0.Without loss of generality, letT1=0. Then, 2≤T2=m−p≤m−1. Let T0=t1,…,tp and T2=tp+1,…,tm. Let tij=Nti∩VQj for p+1≤i≤m and j=0,1. Since VQi−F−T−si≥3n−1−2n−m−1−m−1>m−1≥m−p, there are m−p cycles of length three Ci=wi0,wi1,wi2,wi0 such that wij∈VQj−Fj−Tj−sj for 0≤j≤2 and p+1≤i≤m.Case 3.1.1.T0>T2.SinceT0=p>m−p=T2, we get m≤2p−1. Let W2=wi2:p+1≤i≤m−1 for m−p≥2. Note W2∪s2=m−p=T2 and F2≤2n−m−1≤2n−1−2m−p for m≤2p−1. By Theorem 1, there are m−p disjoint paths Mi=wi2,tip+1≤i≤m−1 and Mm=s2,tm from W2∪s2 to T2 covering Q2−F2.LetW1=wp+11. Note F1≤2n−5. By Lemma 2, there is a Hamilton path L=s1,wp+11 in Q1−F1.LetW0=wi0:p+2≤i≤m−1 for m−p≥3 and W0=∅ for m−p=2. Then, W0=m−p−2. Note T0+W0=p+m−p−2=m−2 and F0≤2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤p and Ri=s,wi0p+2≤i≤m−1 from s to T0∪W0 covering Q0−F0.LetPi=Ri1≤i≤p, Pp+1=ss1∪L∪wp+11wp+12∪Rp+1, Pi=Ri∪wi0wi2∪Mip+2≤i≤m−1 and Pm=ss2∪Mm.Case 3.1.2.T0=T2.SinceT0=p=m−p=T2, we get m=2p≥4. Thus, m−p=p≥2.Case 3.1.2.1.F2=2n−m−1.LetT2′=T2\tp+1. Then, T2′=p−1. Note F1=0. By Lemma 2, there is a Hamilton path L=s1,tp+11 in Q1.LetW2=wi2:p+2≤i≤m−1 for m−p≥3 and W2=∅ for m−p=2. Then, W2=m−p−2=p−2. Note W2∪s2=T2′=p−1 and F2∪tp+1=2n−m=2n−1−2p−1 for m=2p. By Theorem 1, there are p−1 disjoint paths Mi=wi2,tip+2≤i≤m−1 and Mm=s2,tm from W2∪s2 to T2′ covering Q2−F2−tp+1.LetW0=wi0:p+2≤i≤m−1 for m−p≥3 and W0=∅ for m−p=2. Then, W0=m−p−2. Note T0+W0=p+m−p−2=m−2 and F0≤2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤p and Ri=s,wi0p+2≤i≤m−1 from s to T0∪W0 covering Q0−F0.LetPi=Ri1≤i≤p, Pp+1=ss1∪L∪tp+11tp+1, Pi=Ri∪wi0wi2∪Mip+2≤i≤m−1, and Pm=ss2∪Mm.Case 3.1.2.2.F2≤2n−m−2.LetW2=wi2:p+1≤i≤m−1. Note s2∪W2=1+m−p−1=m−p=p=T2 and F2≤2n−m−2=2n−1−2p for m=2p. By Theorem 1, there are p disjoint paths Mi=wi2,tip+1≤i≤m−1 and Mm=s2,tm from W2∪s2 to T2 covering Q2−F2.LetW1=wp+11. Note F1≤2n−5. By Lemma 2, there is a Hamilton path L=s1,wp+11 in Q1−F1.LetW0=wi0:p+2≤i≤m−1 for m−p≥3 and W0=∅ for m−p=2. Then, W0=m−p−2. Note T0+W0=p+m−p−2=m−2 and F0≤2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤p and Ri=s,wi0p+2≤i≤m−1 from s to T0∪W0 covering Q0−F0.LetPi=Ri1≤i≤p, Pp+1=ss1∪L∪wp+11wp+12∪Mp+1, Pi=Ri∪wi0wi2∪Mip+2≤i≤m−1, and Pm=ss2∪Mm.Case 3.1.3.T0<T2.SinceT0=p<m−p=T2, we get m>2p≥2.Case 3.1.3.1.F2≤2n−2m+2p−2.NoteF2≤2n−2m+2p−2=2n−1−2m−p. Let W2=wi2:p+1≤i≤m−1. Note s2∪W2=1+m−p−1=m−p=T2. By Theorem 1, there are m−p disjoint paths Mi=wi2,tip+1≤i≤m−1 and Mm=s2,tm from W2∪s2 to T2 covering Q2−F2.LetW1=wp+11. Note F1≤2n−m−1≤2n−5 for m≥4. By Lemma 2, there is a Hamilton path L=s1,wp+11 in Q1−F1.LetW0=wi0:p+2≤i≤m−1 for m−p≥3 and W0=∅ for m−p=2. Then, W0=m−p−2. Note T0+W0=p+m−p−2=m−2 and F0≤2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤p and Ri=s,wi0p+2≤i≤m−1 from s to T0∪W0 covering Q0−F0.LetPi=Ri1≤i≤p, Pp+1=ss1∪L∪wp+11wp+12∪Mp+1, Pi=Ri∪wi0wi2∪Mip+2≤i≤m−1, and Pm=ss2∪Mm.Case 3.1.3.2.2n−2m+kp−1≤F2≤2n−2m+k+1p−2 for 2p≤kp≤m.Then,F1≤2n−m−1−2n−2m+kp−1=m−kp. Since T2−F1≥m−p−m−kp=k−1p, there are k−1p vertices ti∈T2 such that ti1∉F1. Without loss of generality, let Z=ti:p+1≤i≤kp satisfy above requirement. Let Z1=ti1:p+1≤i≤kp. Then, Z1=Z=k−1p. Let T2′=T2\Z. Let W1=wi1:p+2≤i≤kp for k−1p≥2 and W1=∅ for k−1p=1. Note F1≤m−kp≤2n−1−2k−1p for 2≤2p≤kp≤m≤n. By Theorem 1, there are k−1p disjoint paths Lp+1=s1,tp+11 and Li=wi1,ti1p+2≤i≤kp from W1∪s1 to Z1 covering Q1−F1.Case 3.1.3.2.1.2p≤kp<m.LetW2=wi2:kp+1≤i≤m−1 for m−kp≥2 and W2=∅ for m−kp=1. Note s2∪W2=m−kp=T2\Z and F2∪Z≤2n−2m+k+1p−2+k−1p=2n−2m+2kp−2=2n−1−2m−kp. By Theorem 1, there are m−kp disjoint paths Mi=wi2,tikp+1≤i≤m−1 and Mm=s2,tm from W2∪s2 to T2′ covering Q2−F2−Z.LetW0=wi0:p+2≤i≤m−1 for m−p≥3 and W0=∅ for m−p=2. Then, W0=m−p−2. Note T0+W0=p+m−p−2=m−2 and F0≤2n−m−1≤2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤p and Ri=s,wi0p+2≤i≤m−1 from s to T0∪W0 covering Q0−F0.LetPi=Ri1≤i≤p, Pp+1=ss1∪Lp+1∪tp+11tp+1, Pi=Ri∪wi0wi1∪Li∪ti1tip+2≤i≤kp, Pi=Ri∪wi0wi2∪Mikp+1≤i≤m−1, and Pm=ss2∪Mm.Case 3.1.3.2.2.kp=m.2n−m−1=2n−2m+kp−1≤F2≤2n−2m+k+1p−2=2n−m+p−2≤2n−m−1. Thus, T0=p=1, T2=m−p=m−1, F2=2n−m−1 and F0=F1=0. Let T2′=T2\tm. Then, T2′=m−2. Note F2=2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Mi=s2,ti2≤i≤m−1 from s2 to T2′ covering Q2−F2. Then, tm∈Ri for some 2≤i≤m−1. Without loss of generality, let tm∈Rm−1. Let u and zi be the next vertex of tm and s2 in Rm−1 and Ri for 2≤i≤m−2, respectively. Let u1=Nu∩VQ1 and zi0=Nzi∩VQ0. By the definition of Qn3, zi0∈Ns. Since sti∉EQn3, zi0∉T0. Let Z0=zi0:2≤i≤m−2. By Lemma 2, there is a Hamilton path L=s1,u1 in Q1. Note T0+Z0=m−2. By the induction hypothesis, there are m−2 disjoint paths R1=s,t1 and Ri=s,zi02≤i≤m−2 from s to T0∪Z0 covering Q0−F0.LetP1=R1, Pi=Ri∪zi0zi∪Mizi,ti2≤i≤m−2, Pm−1=ss1∪L∪u1u∪Mm−1u,tm−1 and Pm=ss2∪Mm−1s2,tm.Case 3.2.T1=T2=1.Then,T0=m−2. Let T0=t1,…,tm−2, T1=tm−1 and T2=tm. Note Fi≤2n−5 for 1≤i≤2. By Lemma 2, there is a Hamilton path L=s1,tm−1 and M=s2,tm in Q1−F1 and Q2−F2, respectively. Note F0≤2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤m−2 covering Q0−F0.LetPi=Ri1≤i≤m−2, Pm−1=ss1∪L and Pm=ss2∪M.Case 3.3.Ti≥2 for i=1,2.LetT1=p and T2=q. Since 1≤T0=m−p−q≤m−4, 4≤p+q≤m−1. Without loss of generality, let T1=p≥q=T2. Then, m−3≥p≥q≥2. Since 1≤m−p−q≤m−2q, we get 2q+1≤m. Let T0=t1,…,tm−p−q, T1=tm−p−q+1,…,tm−q and T2=tm−q+1,…,tm.SinceVQi−F−T−si≥3n−1−2n−m−1−m−1≥m−3≥p+q−2, there are p+q−2 cycles Ci=wi0,wi1,wi2,wi0 where wij∈VQj−F−T−sj for m−p−q+2≤i≤m−1 and 1≤j≤2.LetW2=wi2:m−q+1≤i≤m−1 for q≥2. Then, W2∪s2=q=T2. Note F2≤2n−m−1≤2n−1−2q for m≥2q+1 By Theorem 1, there are q disjoint paths Mi=wi2,tim−q+1≤i≤m−1 and Mm=s2,tm from W2∪s2 to T2 covering Q2−F2.Case 3.3.1.m≥2p+1.LetW1=wi1:m−p−q+2≤i≤m−q for p≥2. Then, W1∪s1=p=T1. Note F1≤2n−m−1≤2n−1−2p for m≥2p+1. By Theorem 1, there are p disjoint paths Lm−p−q+1=s1,tm−p−q+1 and Li=wi1,tim−p−q+2≤i≤m−q from s1∪W1 to T1 covering Q1−F1.LetW0=wi0:m−p−q+2≤i≤m−1. Then, W0=p+q−2. Note T0+W0=m−p−q+p+q−2=m−2 and F0≤2n−m−1=2n−1−m−2−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤m−p−q and Ri=s,wi0m−p−q+2≤i≤m−1 from s to T0∪W0 covering Q0−F0.LetPi=Ri1≤i≤m−p−q, Pm−p−q+1=ss1∪Lm−p−q+1, Pi=Ri∪wi0wi1∪Lim−p−q+2≤i≤m−q, Pi=Ri∪wi0wi2∪Mim−q+1≤i≤m−1 and Pm=ss2∪Lm.Case 3.3.2.2p≥m.Case 3.3.2.1.F0≥2p−m+1.NoteF1≤2n−m−1−2p−m+1=2n−2p−2=2n−1−2p. Then, it is similar to Case 3.3.1.Case 3.3.2.2.2p−m−k+1q+1≤F0≤2p−m−kq for 0≤kp≤2p−m.Then,F1≤2n−m−1−2p−m−k+1q+1=2n−2p+k+1q−2 and F0+T0≤2p−m−kq+m−p−q=p−k+1q<p=T1. Since T2−T0−F0≥p−p−k+1q=k+1q, there are k+1q vertices ti∈T1 such that ti0∉F0∪T0. Let tim−p−q+1≤i≤m−p+kq satisfy above requirement. Let Z=ti:m−p−q+1≤i≤m−p+kq and Z0=ti0:m−p−q+1≤i≤m−p+kq. Then, Z=Z0=k+1q. Note T1\Z=p−k+1q≥p−2p−m−q=m−p−q≥1 and F1+Z≤2n−2p+k+1q−2+k+1q=2n−2p+2k+1q−2=2n−1−2p−k+1q.LetW1=wi1:m−p+kq+2≤i≤m−q for k+1q≤2p−m+1≤p−2. Then, W1=p−k+1q−1. By Theorem 1, there are p−k+1q disjoint paths Lm−p+kq+1=s1,tm−p+kq+1 and Li=wi1,tim−p+kq+2≤i≤m−q from W1∪s1 to T1\Z covering Q1−F1−Z.LetW0=wi0:m−p+kq+2≤i≤m−1 for kq≤2p−m≤p−3. Then, W0=p−kq−2. Note T0+Z0+W0=m−p−q+k+1q+p−kq−2=m−2 and F0≤2n−m−1. By the induction hypothesis, there are m−2 disjoint paths Ri=s,ti1≤i≤m−p−q and Ri=s,ti0m−p−q+1≤i≤m−p+kq, Ri=s,wi0m−p+kq+2≤i≤m−1 from s to T0∪Z0∪W0 covering Q0−F0.LetPi=Ri1≤i≤m−p−q, Pi=Ri∪ti0tim−p−q+1≤i≤m−p+kq, Pm−p+kq+1=ss1∪Lm−p+kq+1, Pi=Ri∪wi0wi1∪Lim−p+kq+2≤i≤m−q, Pi=Ri∪wi0wi2∪Mim−q+1≤i≤m−1 and Pm=ss2∪Mm.


## 5. Conclusions

In this paper, we studiedm disjoint paths from S to T covering Qn3−F with F≤2n−2m for 2≤S=T=m≤n. Furthermore, we determined there are m disjoint paths from s to T covering Qn3−F with F≤2n−m−1 where 2≤T=m≤n and s is in a fault-free cycle of length three. In future research, scholars can continue to study vertex disjoint path problem of Qnk or other graphs.



---

*Source: 3953161-2020-08-05.xml*