This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
Introduction
Linear arrays and rings are two of the most important computational structures in interconnection networks. So, embedding of linear arrays and rings into a faulty interconnected network is one of the important issues in parallel processing. An interconnection network is often modeled as a graph, in which vertices and edges correspond to nodes and communication links, respectively. Thus, the embedding problem can be modeled as finding fault-free paths and cycles in the graph with some faulty vertices and/or edges. In the embedding problem, if the longest path or cycle is required the problem is closely related to well-known hamiltonian problems in graph theory. In the rest of this paper, we will use standard terminology in graphs(see ref.[2]). It is very difficult to determine that a graph is hamiltonian or not. Readers may refer to [4,5,6].
Definitions and Notation
We follow [2] for graph-theoretical terminology and notation not defined here. A graph G = (V,E) always means a simple graph(without loops and multiple edges), where V = V(G) is the vertex set and E = E (G) is the edge set. The degree of a vertex v is denoted by d(v) = dG(v), whereas d = δ(G) and Δ = Δ(G) stand for the minimum degree and the maximum degree of G, respectively. A path is a sequence of adjacent vertices, denoted by x1x2· · · xl, in which all the vertices x1,x2, · · · ,xl are distinct. Let path P = x1,x2, · · · ,x‘ and P[xi,xj] denotes the sequence of adjacent vertices from xi to x j on path P. That is, P[xi,xj] = xixi+1· · ·xj-1xj. For two vertices u,v ϵ V(G), a path joining u and v is called a uv-path. A path P in graph G is call a Hamiltonian path if V(P) = V(G). A cycle is a path such that the first vertex is the same as the last one. A cycle is also denoted by x1x2· · · xlx1. Length of a cycle is the number of edges in it. An ‘-cycle is a cycle of length l. Let c(G) = max{l : ‘-cycle of G}. A cycle of G is called Hamiltonian cycle if its length is |V(G)|. A graph G is Hamiltonian if G contains a Hamiltonian cycle. A graph G is Hamiltonian-connected if any two vertices u,v 2 V(G) exists a Hamiltonian uv-path.
Two edges xy,uv 2 E (G) are called independent if {x,y}∩{u,v} = / 0. A matching is a set of edges that are pairwise independent. A perfect matching between two disjoint graphs G1, G2 with the same order n is a matching consisting of n edges such that each of them has one end vertex in G1 and the other one in G2. See [7, 8, 9, 10, 11, 12, 13, 14].
The construction of new graphs from two given ones is not unusual at all. Basically, the method consists of joining together several copies of one graph according to the structure of another one, the latter being usually called the main graph of the construction. In this regard, Chartrand and Harary introduced in [3] the concept of permutation graph as follows. For a graph G and a permutation π of V(G), the permutation graph Gπ is defined by taking two disjoint copies of G and adding a perfect matching joining each vertex v in the first copy to π(v) in the second. Examples of these graphs include hypercubes, prisms, and some generalized Petersen graphs. The product graph Gm * Gp of two given graphs Gm and Gp, defined in [1] by Bermond et al. in the following way.
Definition 1. Let Gm = (V(Gm),E(Gm)) and Gp = (V(Gp),E(Gp)) be two graphs. Let us give an arbitrary orientation to the edges of Gm, in such a way that an arc from vertex x to vertex y is denoted by exy. For each arc exy, let πexy be a permutation of V(Gp). Then the product graph Gm *Gp has V(Gm)×V(Gp) as vertex set, with two vertices (x,x'), (y,y') being adjacent if either
$$x=y\quad \quad \quad and \quad \quad \quad x'y'\in E(G_{p})$$
or
$$xy\in E(G_{m})\quad \quad \quad and \quad \quad \quad y'=\pi_{e_{xy}}(x').$$
The product graph Gm * Gp can be viewed as formed by |V(Gm)| disjoint copies of Gp, each arc exy, indicating that some perfect matching between the copies $G_{p}^{x}, G_{p}^{y}$( respectively generated by the vertices x and y of Gm) is added. So the graph Gm is usually called the main graph and Gp is called the pattern graph of the product graph Gm * Gp . Moreover, every edge of Gm * Gp that belongs to any of the |E(Gm)| perfect matchings between copies of Gp is an cross edge of Gm * Gp.
Observe that if we choose πexy(x') = x' for any arc exy then Gm * Gp = Gm□Gp. Furthermore, if Gm is K2 we have K2* G = G* , a permutation graph. Hence, Gm * Gp can be considered as a generalized permutation graph.
Definition 2. A graph G is called f -fault hamiltonian (resp. f -fault hamiltonian-connected) if there exist a hamiltonian cycle (resp. if each pair of vertices are joined by a hamiltonian path) in G -F for any set F of faulty elements with |F| ≤ f.
If a graph G is f -fault hamiltonian (resp. f -fault hamiltonian-connected), then it is necessary that f ≤ δ(G)-2 (resp. f ≤ δ(G)-3), where δ(G) is the minimum degree of G.
Definition 3. A graph G is call f -fault q-panconnected if each pair of fault-free vertices are joined by a path in G -F of every length from q to |V(G-F)|-1 inclusive for any set F of fault elements with |F| ≤ f.
When we are to construct a path from s to t, s and t are called a source and a sink, respectively, and both of them are called terminals. When we find a path/cycle, sometimes we regard some fault-free vertices and edges as faulty elements. They are called virtual faults.
Main Results
For the sake of convenience, we write m(p) for the order of Gm( Gp, respectively.) Suppose V(Gm) = {x1,x2, · · · ,xm} and V(Gp) = {y1,y2, · · · ,yp}.
Theorem 1
If Gm is hamiltonian, and Gp is hamiltonian-connected, then Gm * Gp is also hamiltonian-connected.
Proof. Choose two vertices in u,v ϵ V(Gm * Gp). We have the following cases:
Case 1. u,v belong to the same subgraph, say, $G_P^{x_1}$. Since Gm is hamiltonian, suppose hamiltonian-cycle C = x1x2· · ·xm. Since $G_P^{x_1}$is hamiltonian-connected, u,v are connected by a hamiltonian-path P1 in $G_P^{x_1}$, suppose P1 = (x1,y1)(x1,y2) · · · (x1,yp), where (x1,y1) = u, (x1,yp) = v. Since x1xm ϵ E(Gm), suppose (x1,y2)(xm,y2) ϵ E (Gm * Gp). Then u,v are connected by a hamiltonian-path P' in Gm * Gp by choosing the endvertex, say, (x2,y1) of cross edge (x1,y1)(x2,y1) and have a hamiltonian-cycle C2 passing (x2,y1) in $G_p^{x_2}.$Suppose the last vertex is (x2,yp) in C2, and choosing the endvertex, say, (x3,yp) of cross edge (x3,yp)(x2,yp) and have a hamiltonian-cycle C3 passing (x3,yp) in $G_p^{x_3}.$Suppose the last vertex is (x3,yl) in C3, and so on, choosing the endvertex, say, (xm,yj) (1 ≤ j ≤ p ) of cross edge (xm-1,y1)(xm,yj) and choosing the endvertex (xm,y2) of cross edge (x1,y2)(xm,y2), have a hamiltonian-path Pm passing (xm,yj) and (xm,y2) in $G_p^{x_m}.$Let P' = u(x2,y1)∪C2[(x2,y1),(x2,yp)]∪(x2,yp)(x3,yp)∪C3[(x3,yp),(x3,yl)]∪· · ·∪(xm-1,y1)(xm,yj)∪ Pm[(xm,yj),(xm,y2)]∪(xm,y2)(x1,y2)∪P1[(x1,y2),v]. Then we obtain the desired result.
Case 2. u,v belong to two subgraphs, suppose $G_P^{x_1}$, $G_P^{x_i}$(1 ≤ i ≤ m). and $u\in G_P^{x_1}$and $v\in G_P^{x_i}.$Suppose u = (x1,y1), v = (xi,yj) (1 ≤ j ≤ p) . Since Gm is hamiltonian, suppose hamiltonian-cycle C = x1x2· · ·xmx1. Since $G_P^{x_1}$is hamiltonian-connected, u belongs to a hamiltonian-cycle C1 in $G_P^{x_1}$, suppose C1 = (x1,y1)(x1,y2) · · · (x1,yp)(x1,y1), where (x1,y1) = u.
Then u,v are connected by a hamiltonian-path P' in Gm * Gp by choosing the endvertex, say, (x2,y1) and (x2,y2) of cross edges (x1,y1)(x2,y1) and (x1,y2)(x2,y2). Then there exist a hamiltonian-path P2 connecting (x2,y1) and (x2,y2) in $G_P^{x_2}$ since $G_P^{x_2}$is Hamilton-connected. Taking adjacent vertices (x2,yt) and (x2,yt+1) in path P2, then P2 = P21∪(x2,yt)(x2,yt+1)[P22, where P21 = P2[(x2,y1), (x2,yt)] and P22 = P2[(x2,yt+1), (x2,y2)]. Choosing the endvertices , say, (x3,yt) and (x3,yt+1) of cross edges (x3,yt)(x2,yt) and (x3,yt+1)(x2,yt+1). Then there exist a hamiltonian-path P3 connecting (x3,yt) and (x3,yt+1) in $G_p^{x_3}$since $G_p^{x_3}$is Hamilton-connected. Taking adjacent vertices (x3,yj) and (x3,yj+1) in path P3, then P3 = P31∪ (x3,yj)(x3,yj+1) ∪ P32, where P31 = P3[(x3,yt), (x3,yj)] and P32 = P3[(x3,yj+1), (x3,yt+1)], and so on. Until we take adjacent vertices (xi-2,ym) and (xi-2,ym+1) in path Pi-2, and the endvertices, say, (xi-1,ym) and (xi-1,ym+1) of cross edges (xi-1,ym )(xi-2,ym) and (xi-1,ym+1)(xi-2,ym+1). Then there exist a hamiltonian-path Pi-1 connecting (xi-1,yμ) and (xi-1,yμ+1) in $$G_p^{x_{i-1}}$$ since $$G_p^{x_{i-1}}$$ is Hamilton-connected. Let path $P'_1=u(x_2, y_1)\cup P_{21}\cup (x_2, y_t)(x_3, y_t)\cup P_{31}\cup \cdots \cup P_{(i-2)1}\cup (x_{i-2}, y_{\mu})(x_{i-1}, y_{\mu })\cup P_{i-1}\cup (x_{i-1}, y_{\mu +1})(x_{i-2}, y_{\mu +1 })\cup P_{(i-2)2}\cup \cdots \cup P_{32}\cup (x_3, y_{t+1})(x_2, y_{t+1})\cup P_{22}\cup (x_2, y_2)(x_1, y_2)\cup C_1[(x_1, y_2), (x_1, y_p)]$.
Choosing the endvertex, say, (xm,yp) of cross edge (x1,yp)(xm,yp). Then there exist a hamiltonian-cycle Cm passing (xm,yp) in $G_p^{x_m}$since $G_p^{x_m}$is Hamilton-connected. Suppose the last vertex is (xm,y1) in Cm, taking the endvertex, say, (xm-1,yp) of cross edge (xm,y1)(xm-1,yp). Then there exist a hamiltonian-cycle Cm-1 passing (xm-1,yp) in $G_p^{x_{m-1}}$ since $G_p^{x_{m-1}}$ is Hamilton-connected, and so on. Until we take the last vertex, say, (xi+1,y1) in Ci+1, taking the endvertex, say, (xi,yp) of cross edge (xi+1,y1)(xi,yp).
If (xi,yp) = (xi,yj). Then there exist a hamiltonian-cycle Ci passing (xi,yp) in $G_p^{x_{i}}$since $G_p^{x_{i}}$is Hamilton-connected, taking the adjacent vertex of (xi,yj), say, (xi,yj-1) in cycle Ci and taking the endvertex, say, (xi+1,yj-1) of cross edge (xi+1,yj-1)(xi,yj-1) (if (xi+1,yj-1) = (xi+1,yp), then taking the other adjacent vertex of (xi,yj) such that (xi+1,yj-1) ≠ (xi+1,yp)). Then there exist a hamiltonian-path Pi+1 connecting (xi+1,yp) and (xi+1,yj-1) in $G_p^{x_{i+1}}$since $G_p^{x_{i+1}}$is Hamilton-connected. Let $P''_2=(x_1, y_p)(x_m, y_p)\cup C_m[(x_m, y_p), (x_m, y_1)]\cup (x_m, y_1)(x_{m-1}, y_p)\cup C_{m-1}[(x_{m-1}, y_p), (x_{m-1}, y_1)]\cup \cdots \cup C_{i+1}[(x_{i+1}, y_{p}), (x_{i+1}, y_{1})]\cup (x_{i+1}, y_{1})(x_i, y_{p})\cup P_i[(x_i, y_{p}), v]$
If (xi,yp) ≠ (xi,yj). Then there exist a hamiltonian-path Pi connecting (xi,yp) and (xi,yj) in $G_p^{x_{i}}$since $G_p^{x_{i}}$is Hamilton-connected. Let $P''_2=(x_1, y_p)(x_m, y_p)\cup C_m[(x_m, y_p), (x_m, y_1)]\cup (x_m, y_1)(x_{m-1}, y_p)\cup C_{m-1}[(x_{m-1}, y_p), (x_{m-1}, y_1)]\cup \cdots \cup C_{i+1}[(x_{i+1}, y_{p}), (x_{i+1}, y_{1})]\cup (x_{i+1}, y_{1})(x_i, y_{p})\cup P_i[(x_i, y_{p}), v]$
Let $P'=P'_1\cup P''_2$Then we obtain the desired result. 2
Corollary 2. If Gm and Gp are hamiltonian-connected, then Gm * Gp is also hamiltonian-connected.
Corollary 3. If Gm and Gp are hamiltonian, then,
c(Gm * Gp) ≥ mp — p,
There exists a hamiltonian path in Gm * Gp.
Proof. Since Gm is Hamiltonian, suppose Hamiltonian-cycle C' = x1x2· · · xmx1. Since Gp is Hamiltonian, suppose Hamiltonian-cycle C" = y1y2· · ·ypy1.
We obtain a cycle C as follows: Choosing any vertex, say, (x1,y1), in $V(G_p^{x_1})$. Taking the endvertex, say, (x2,y1), of cross edge (x1,y1)(x2,y1) and have a hamiltonian-cycle C2 passing (x2,y1) in $G_p^{x_{2}}$. Suppose the last vertex is (x2,yp) in C2. Taking the endvertex, say, (x3,y1), of cross edge (x2,yp)(x3,y1) and have a hamiltonian-cycle C3 passing (x3,y1) in $G_p^{x_{3}}$The last vertex is (x3,yp) in C3, · · · , and so on, until taking the endvertex, say, (xm,y1), of cross edge (xm,y1)(xm-1,yp) and have a hamiltonian-cycle Cm passing (xm,y1) in $G_p^{x_{m}}$The last vertex is (xm,yp) in Cm. Taking the endvertex, say, (x1,yj), of cross edge (xm,yp)(x1,yj) and have a hamiltonian-cycle C1 passing (x1,yj) in $G_p^{x_{1}}$. So the length of ((x1,yj), (x1,y1))-path in $G_p^{x_{1}}$is at least $\lfloor \frac{p}{2}\rfloor$, but if (x1,yj) = (x1,y1), then (i) holds.
We obtain a Hamiltonian path as follows: Choosing any vertex, say, (x1,y1), in $V(G_p^{x_1})$, and have a hamiltonian-cycle C1 passing (x1,y1) in $G_p^{x_{1}}$The last vertex is (x1,yp) in C1. Taking the endvertex, say, (x2,y1), of cross edge (x1,yp)(x2,y1) and have a hamiltonian-cycle C2 passing (x2,y1) in $G_p^{x_{2}}$The last vertex is (x2,yp) in C2. Taking the endvertex, say, (x3,y1), of cross edge (x2,yp)(x3,y1) and have a hamiltonian-cycle C3 passing (x3,y1) in $G_p^{x_{3}}$The last vertex is (x3,yp) in C3, · · · , and so on, until taking the endvertex, say, (xm,y1), of cross edge (xm,y1)(xm-1,yp) and have a hamiltonian-cycle Cm passing (xm,y1) in $G_p^{x_{m}}$. The last vertex is (xm,yp) in Cm. Then we obtain hamiltonian-path ((x1,y1), (xm,yp))-path. $\Box$
Corollary 4
If there exists hamiltonian path in Gm, Gp is hamiltonian, then there exists a hamiltonian path in Gm * Gp
Fi denote the sets of faulty elements in $G_p^{x_i}, 1\leq i \leq m$.F0 denotes the set of faulty edges in cross edge-set. |Fi| = fi, 0 ≤ i ≤ m. We denote by $f_v^{x_1}, f_v^{x_2}, \cdots, f_v^{x_m}$ the number of faulty vertices in $G_p^{x_1}, G_p^{x_2}, \cdots, G_P^{x_m}$,respectively, and by fv the number of faulty vertices in Gm * Gp, so that $f_v = f_v^{x_1} + f_v^{x_2} + \cdots + f_v^{x_m}$.Note that the length of a hamiltonian path in Gm * Gp-F is mp — fv-1.
Theorem 5
Let Gm have a hamiltonian-path, Gp is f -fault hamiltonian-connected and f +1-fault hamiltonian, p ≥ 3 f +6, then,
for any f ≥ 1, Gm * Gp is f +2-fault hamiltonian, and
for f = 0, Gm * Gp with 2 faulty elements has a hamiltonian cycle unless one faulty element is contained in$G_p^{x_{i}}$and the other faulty element is contained in$G_p^{x_{j}}, i\ne j, 1\leq i , j\leq m$
Proof. (a) Suppose C = x1x2· · ·xm is hamiltonian-path in Gm. Assuming the number of faulty elements |F| ≤ f +2, we will construct a cycle of length l, l = mp — fv, in Gm * Gp-F.
Case 1. fi ≤ f , 0 ≤ i ≤ m. Taking two adjacent vertices u,$v\in V(G_p^{x_1}- F_1)$. Since Gp is f -fault hamiltonian-connected, there exists hamiltonian uv-path, say, P1, in $G_p^{x_1}-F_1$.. We first claim that there exist an edge (x,y) on P1 such that all of x̄, (x, x̄ x̄), ȳ, and (y, ȳ) do not belong to F, where $\bar{x}, \bar{y}\in G_p^{x_2}, (x, \bar{x}), (y, \bar{y})$are two cross edges. Since there are $p-f_v^{x_1}-1$candidate edges on P1 and at most f +2 faulty elements can “block” the candidates, at most two candidates per one faulty element. By assumption p ≥ 3 f +6, and the claim is proved. The path P12 can be obtained by merging P1 and a hamiltonian-path P2 in $G_p^{x_2}- F_2$between x̄, ȳ with the edges (x, x̄), (y, ȳ ), of course the edge (x,y) is discarded. Similarly, there exist an edge (x',y') on P2 such that all of $\bar{x'}, (x', \bar{x'}), \bar{y'}$,and $(y', \bar{y'})$do not belong to F, where $\bar{x'}, \bar{y'}\in G_p^{x_3}, (x', \bar{x'}), (y', \bar{y'})$are two cross edges. The path P123 can be obtained by merging P12 and a hamiltonian-path P3 in $G_p^{x_3}- F_3$between $\bar{x'}, \bar{y'}$with the edges $(x', \bar{x'}), (y', \bar{y'})$,of course the edge (x',y') is discarded, and so on, at least we obtain the hamiltonian-path P12· · · m in Gm * GP -F. Therefore P12· · · m∪ uv is hamiltonian-cycle in Gm * GP-F.
Case 2. There exists some i, j such that fi = f +1, fj = 1. Then ft = 0, 0 ≤ t ≤ m, t ≠ i, j. Since f ≥ 1.
Subcase 2.1. i = 0. Taking two adjacent vertices $u, v\in V(G_p^{x_1}- F_1)$.Since Gp is f -fault hamiltonian-connected, there exists hamiltonian uv-path, say, P1, in $G_p^{x_1}-F_1$.Similar to Case 1, it follows that Gm * Gp is f +2-fault hamiltonian.
Subcase 2.2. i = 1. Since Gp is f + 1-fault hamiltonian, Taking hamiltonian cycle in $G_P^{x_1}- F_1$.Similar to Case 1, it follows that Gm * Gp is f +2-fault hamiltonian.
Subcase 2.3. i 6= 1, 0. Since Gp is f +1-fault hamiltonian, Taking hamiltonian cycle Ci in $G_P^{x_i}- F_i$.Since fi = f +1, fj = 1. Then ft = 0, 0 ≤ t ≤ m, t ≠ i, j, then there exist two adjacent edges (x,y), (y,z) on Ci such that all of x̄, (x, x̄), ȳ, and (y, ȳ) , z0, and (z, z'), and (y,y') do not belong to F, where $\bar{x}, \bar{y}\in G_p^{x_{i+1}}$,and $y', z'\in G_p^{x_{i-1}}$,(x, x̄), (y, ȳ), (y,y'), (z, z') are cross edges. Similar to Case 1, $G_p^{x_{i-1}}$has hamiltonian path Pi-1 connecting the vertex y', z' and $G_p^{x_{i+1}}$has hamiltonian path Pi+1 connecting the vertex ȳ, x̄. We obtain a cycle C(i-1)i(i+1) by merging Ci and hamiltonian path Pi-1,Pi+1 with the edges (x, x̄), (y, ȳ),(z, z'), (y,y'), of course the edges (x,y) and (y, z) are discarded. Taking an edge α;β in Pi-1 and Pi+1, respectively. Similar to Case 1, at least we obtain cycle C12· · · m, then Gm * Gp is f +2-fault hamiltonian.
Case 3. There exists some fi such that fi = f +2. Then fj = 0, 0 ≤ j ≤ m, j ≠ i.
Subcase 3.1. i = 0. Taking two adjacent vertices u,$u, v\in V(G_p^{x_1}- F_1)$.Since Gp is f -fault hamiltonian-connected, there exists hamiltonian uv-path, say, P1, in $G_p^{x_1}-F_1$.. Since p ≥ 3 f +6, then there exist an edge (x,y) on P1 such that all of ȳ, (x, x̄), ȳ, and (y, ȳ) do not belong to F, where $\bar{x}, \bar{y}\in G_p^{x_2}, (x, \bar{x}), (y, \bar{y})$are two cross edges. Similar to Case 1, it follows that Gm * Gp is f +2-fault hamiltonian.
Subcase 3.2. i = 1. Since Gp is f +1-fault hamiltonian, we select an arbitrary faulty element a in $G_p^{x_i}$.. Regarding a as a virtual fault-free element. Taking hamiltonian cycle C1 in $G_P^{x_1}- F_1$.. If a is a faulty vertex on C1, let x and y be two vertices on C1 next to a, else if C1 passes through the faulty edge a, let x and y be the endvertices of a. The cycle C12 is obtained by merging C1-α and a hamiltonian-path in $G_P^{x_2}$ joining x̄ and ȳ with cross edges (x, x̄), (y, ȳ), where $\bar{x},\bar{y}\in V(G_p^{x_2})$.Similar to Case 1, it follows that Gm * Gp is f +2-fault hamiltonian.
Subcase 3.3. i 6= 1, 0. Since Gp is f +1-fault hamiltonian, we select an arbitrary faulty element a in $G_p^{x_i}$. Regarding a as a virtual fault-free element. Taking hamiltonian cycle Ci in $G_P^{x_1}- F_i$.If a is a faulty vertex on Ci, let x and y be two vertices on Ci next to a, else if Ci passes through the faulty edge a, let x and y be the endvertices of a. Let z be the vertices on Ci next to y. The cycle C(i-1)i(i+1) is obtained by merging Ci - α and a hamiltonian-path in $G_P^{x_{i+1}}$ joining x̄ and ȳ and a hamiltonian-path in $G_P^{x_{i-1}}$ joining z' and y' with cross edges (z, z'), (y,y'), (x, x̄), (y, ȳ), where $z',y'\in V(G_p^{x_{i-1}})$and $ \bar{x}, \bar{y} \in V(G_p^{x_{i+1}})$. Similar to Subcase 2.3, it follows that Gm * Gp is f +2-fault hamiltonian.
(b) If f = 0. Since Gp is 0-fault hamiltonian-connected and 1-fault hamiltonian, we have similar proof subcase 3.2 by regarding a faulty element as virtual faulty-free element if the two faulty elements is contained in subgraph $G_p^{x_i}$. This completes the proof. $\Box$
Corollary 6. Let Gm = K2, Gp is f -fault hamiltonian-connected and f +1-fault hamiltonian, p ≥ 3 f +6, then,
for any f ≥ 1, K2* Gp is f +2-fault hamiltonian.
for f = 0, K2* Gp with 2 faulty elements has a hamiltonian cycle unless one faulty element is contained in$G_p^{x_{1}}$and the other faulty element is contained in$G_p^{x_{2}}$.
Theorem 7
Let Gm have a hamiltonian-path, Gp is f -fault q-panconnected and f +1-fault hamiltonian, p ≥ 2q+ f +2, q ≥ 2 f +5, then,
for any f ≥ 2, Gm * Gp is f +1-fault q+m-panconnected,
for f = 1, Gm * Gp with 2 faulty elements has a path of every length q +m or more joining s and t unless s and t are contain in the same subgraph$G_p^{x_i}$and their neighbors are the faulty element in$G_p^{x_j}, i\ne j$,
for f = 0, Gm * Gp with 1 faulty element has a path of every length q +m or more joining s and t unless s and t are contained in the same subgraph$G_p^{x_i}$and one of their neighbors is the faulty element in$G_p^{x_j}, i\ne j$,
Proof.
Suppose P =x1x2· · ·xm is a hamiltonian-path of Gm. Assuming the number of faulty elements |F|≤ f +1, we will construct a path of every length L, q +m ≤ L ≤ mp — fv-1, in Gm * Gp — F joining any pair of vertices s and t.
Case 1. fi ≤ f , 0 ≤ i ≤ m.
Subcase 1.1. When both s, t is contained in $G_p^{x_1}$. There exists a path P1 of length l1 in $G_p^{x_1}$joining s and t for every $q\leq \ell_1 \leq p-f_v^{x_1}-1$. We are to construct a longer path P12 that passes through vertices in $G_p^{x_1}$and $G_p^{x_2}$. We first claim that there exist one edge (x,y), on P1 such that all of x̄, (x, x̄), ȳ, and (y, ȳ), do not belong to F, where $\bar{x}, \bar{y}\in G_p^{x_2}, (x, \bar{x}), (y, \bar{y})$are two cross edges. Since there are l1 candidate edges on P1 and at most f +1 faulty elements can "block" the candidates, at most two candidates per one faulty element. By assumption q ≥ 2 f +5, and the claim is proved. The path P12 can be obtained by merging P1 and a path P2 in $G_p^{x_2}-F_2$between x̄, ȳ with the edges (x, x̄), (y, ȳ), of course the edge (x,y) is discarded. Let l2 be the length of P2, the length l12 of P12 can be anything in the range $2q+1\leq \ell_{12} \leq \ell_1 +\ell_2 +1 \leq 2p-f_v^{x_1}-f_v^{x_2} -1$. Since $p\geq 2q+f+2, f_v^{x_i}\leq f$, we have $2q +1 \leq p-f_v^{x_1}-1$. So there exist path connecting the vertex s and t such that the length of path can be anything in the range $[q, 2p-f_v^{x_1}-f_v^{x_2} -1]$. Similarly, we claim that there exist one edge (u,v), on P2 such that all of ū , (u, ū), ⊽, and (v, ⊽), do not belong to F, where $\bar{u}, \bar{v}\in G_p^{x_3}, (u, \bar{u}), (v, \bar{v})$are two cross edges. The path P123 can be obtained by merging P12 and a path P3 in $G_p^{x_3}-F_3$between ū, ⊽ with the edges (u, ū), (v, ⊽), of course the edge (u,v) is discarded. Let l3 be the length of p3, the length l123 of P123 can be anything in the range $3q+2\leq \ell_{123} \leq \ell_{12} +\ell_3 +1 \leq 3p-f_v^{x_1}-f_v^{x_2}-f_v^{x_3} -1$Since $p\geq 2q+f+2, f_v^{x_i}\leq f$we have $2q +1 \leq p-f_v^{x_1}-1$and $3q +2 \leq 2p-f_v^{x_1}-f_v^{x_2}-1$and so on, at least the path P12· · · m, and q ≤ l12· · ·m≤ mp — fv-1.
Subcase 1.2. When both s, t is contained in $$G_p^{x_i}, i\ne 1$$. We first claim that there exist two edges (x,y), (u,v) on Pi such that all of x̄, (x, x̄), ȳ, and (y, ȳ), ū, (u, ū), ⊽, and (v, ⊽) do not belong to F, where $\bar{x}, \bar{y} \in G_p^{x_{i+1}}, \bar{u}, \bar{v}\in G_p^{x_{i-1}}$and (x, x̄), (y, ȳ), (u, ū), (v, ⊽) are four cross edges. Since there are l1 candidate edges on P1 and at most f +1 faulty elements can "block" the candidates, at most two candidates per one faulty element. By assumption q ≥ 2 f +5, and the claim is proved. The path P(i-1)i(i+1) can be obtained by merging Pi and two paths Pi-1, Pi+1 in $G_p^{x_{i-1}}-F_{i-1}, G_p^{x_{i+1}}- F_{i+1}$respectively, between ū, ⊽ with the edges (u, ū), (v, ⊽), and x̄, ȳ with the edges (x, x̄), (y, ȳ), of course the edge (u,v), (x,y) is discarded. Similar to Subcase 1.1, it follows that the path P12· · · m, and q ≤ l12· · · m≤ mp — fv-1.
Subcase 1.3. When s is in $G_p^{x_i}$, t is in $$G_p^{x_j}, i\ne j$$. Since G is f -fault hamiltonian-connected, then f ≤ δ(G)-3, where δ(G) is the minimum degree of G, then there exist one adjacent vertex $S'\in G_p^{x_i}$ of s such that the cross edges sequence T ∉ F, where $T = s'(x_{i+1}, y^{i+1}), (x_{i+1}, y^{i+1})(x_{i+2}, y^{i+2}),\cdots, (x_{j-1}, y^{j-1})(x_{j}, y^{j})$ where =$(x_{i+1}, y^{i+1})\in G_p^{x_{i+1}}, (x_{i+2}, y^{i+2})\in G_p^{x_{i+2}}, (x_{j-1}, y^{j-1})\in G_p^{x_{j-1}}, (x_{j}, y^{j})\in G_p^{x_{j}}$ There exists a path P1 of length l1 in $G_p^{x_j}$ joining t and (xj,yj) for every $q\leq \ell_1 \leq p-f_v^{x_j}-1$. Hence a path $P_1'$ joining s and t can be obtained by merging P1 and the cross edges sequence T with the length $\ell_1'$of path P1 for every integer in the range $q+j-i+1\leq \ell_1' \leq p-f_v^{x_j}+j-i-1$. Similarly to Subcase 1.2, it follows that the result completes.
Case 2. There exists some fi such that fi = f +1. Then fj = 0, 1 ≤ j ≤ m, j ≠ i. Since f ≥ 2. Similar to case 1, it follows that the result completes.
It immediately follows from Case 1, where the assumption f ≥ 2 is never used, that f = 0, 1, Gm * Gp with f +1 faulty elements has a path of every length q +m or more joining s and t unless s and t are contained in the same subgraph $G_p^{x_i}$ and one of their neighbors is the faulty element in $$G_p^{x_j}, i\ne j$$. Thus, the proof of (c) is done. we testify the case (b), note that Gp is 1-fault q-panconnected. This completes the proof.
