Abstract
A one-to-one k-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) of a graph G is a collection of k internally vertex disjoint paths joining source with sink that cover all vertices of G. In this paper, we investigate the problem of one-to-one disjoint path cover in hypercubes with faulty edges and obtain the following results: Let u, v ∈ V(Qn) be such that \(p(u)\ne p(v)\) and \(1\le k\le n\). Then there exists a one-to-one k-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) joining vertices u and v in \(Q_n\). Moreover, when \(1\le k\le n-2\), the result still holds even if removing \(n-2-k\) edges from \(Q_n\).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
A topological structure of an interconnection network can be modeled by a graph \(G=(V(G),E(G))\), where the vertex set V(G) represents the set of processors and the edge set E(G) represents the set of links joining processors. One of the most central issues in various interconnection networks is to find vertex disjoint paths concerned with a routing among vertices [1,2,3,4,5,6, 33, 34].
A u, v-path is a path with endpoints u and v, denoted by \(P_{u,v}\) when we specify a particular such path. We say that k paths are vertex disjoint in a graph G if any two of them have no common vertex. Given any two disjoint sets of k labeled vertices \(S=\{s_1,s_2,\ldots ,s_k\}\) and \(T=\{t_1,t_2,\ldots ,t_k\}\) in a graph G, are there k vertex disjoint paths \(P_{s_1,t_1},P_{s_2,t_2},\ldots ,P_{s_k,t_k}\) which cover all vertices of G?
It has been investigated with respect to various special graphs such as hypercubes [8, 12, 17, 18, 21, 24, 25], k-ary n-cubes [30, 35, 36], and hypercube-like interconnection networks [13, 28, 29].
A path (respectively, cycle) in a graph G is a hamiltonian path (respectively, hamiltonian cycle) if every vertex in G appears exactly once in the path (respectively, cycle). One of the core subjects in hamiltonian graph theory is to develop sufficient conditions for a graph to have a hamiltonian path/cycle [14, 15, 19, 20, 26, 27, 31].
Fault tolerance is an important index of the stability of the network. It is useful to consider faulty networks because node faults or link faults may occur in networks. In this regard, the fault-tolerant capacity of a network is a critical issue in parallel computing. It motivated the study of various networks with faulty elements [10, 11, 16, 17, 21].
The n-dimensional hypercube, denoted by \(Q_{n}\), is one of the most popular and efficient interconnection networks. Hypercubes play an important role in many areas of computer science. Motivated by the disjoint path cover problem and Hamilton problem, we consider the problem of one-to-one k-disjoint path cover in hypercubes with faulty edges.
A one-to-one k-disjoint path cover\(\{P_1,P_2,\ldots ,P_k\}\) of a graph G is a collection of k internally vertex disjoint paths joining source with sink that cover all vertices of G. Denote the source and sink by u and v, respectively. Then the one-to-one k-disjoint path cover joining u and v sometimes is called by u-to-vk-disjoint path cover.
Studies about one-to-one disjoint path cover problem of some networks or graphs can be found in the literature [9, 30]. In this paper, we investigate the problem of one-to-one disjoint path cover in hypercubes and obtain the following results: Let \(u,v\in V(Q_n)\) be such that \(p(u)\ne p(v)\) and \(1\le k\le n\). Then there exists a u-to-vk-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) in \(Q_n\). Moreover, when \(1\le k\le n-2\), the result still holds even if removing \(n-2-k\) edges from \(Q_n\).
2 Definitions and preliminaries
Terminology and notation used in this paper but undefined below can be found in [7]. Let G be a graph. For a set \(F\subseteq E(G)\), let \(G-F\) denote the resulting graph after removing all edges in F from G. For a set \(S\subseteq V(G)\), let \(G-S\) denote the graph removing all vertices in S and all the edges incident with S from G.
Let \(P_{x,y}=(x,\ldots ,v_i,\ldots ,v_j,\ldots ,y)\) be a path. We use \(P_{x,y}[v_i,v_j]\) to denote the subpath \((v_i,\ldots ,v_j)\) of \(P_{x,y}\) joining \(v_i\) and \(v_j\). For two paths \(P_1\) and \(P_2\) with only one common endpoint, we use \(P_1+P_2\) to denote the path P such that \(V(P)=V(P_1)\cup V(P_2)\) and \(E(P)=E(P_1)\cup E(P_2)\).
Let [n] denote the set \(\{1,\ldots ,n\}\). The n-dimensional hypercube\(Q_{n}\) is a graph whose vertex set consists of all binary strings of length n, i.e., \(V(Q_n)=\{u: u=\delta _1\cdots \delta _n\) and \(\delta _i\in \{0,1\}\) for every \(i\in [n]\}\), with two vertices being adjacent whenever the corresponding strings differ in just one position. The Hamming distance between two vertices u and v in \(Q_n\), denoted by d(u, v), is the number of different bits of u and v.
Let \(j\in [n]\). An edge in \(Q_n\) is an j-edge if its endpoints differ in the jth position. The set of all j-edges in \(Q_n\) is denoted by \(E_j\). Let \(Q_{n-1,j}^0\) and \(Q_{n-1,j}^1\), with the superscripts j being omitted when the context is clear, be the \((n-1)\)-dimensional subcubes of \(Q_n\) induced by the vertex sets \(\{u=\delta _1\cdots \delta _n\in V(Q_n): \delta _j=0\}\) and \(\{u=\delta _1\cdots \delta _n\in V(Q_n): \delta _j=1\}\), respectively. Thus \(Q_n-E_j=Q_{n-1,j}^0+Q_{n-1,j}^1\). We say that \(Q_n\)splits into two \((n-1)\)-dimensional subcubes \(Q_{n-1}^0\) and \(Q_{n-1}^1\) at position j. See Fig. 1 for example.
Let \(\alpha \in \{0,1\}\). We use \(\bar{\alpha }\) to denote \(1-\alpha \). Every vertex \(x^\alpha \in V(Q_{n-1}^\alpha )\) has in \(Q_{n-1}^{\bar{\alpha }}\) a unique neighbor, denoted by \(x^{\bar{\alpha }}\).
Moreover, we may split \(Q_{n-1}^\alpha \) into two \((n-2)\)-dimensional subcubes \(Q_{n-2}^{\alpha 0}\) and \(Q_{n-2}^{\alpha 1}\) at some position i. So \(Q_n-E_j-E_i=Q_{n-2}^{00}+Q_{n-2}^{01}+Q_{n-2}^{10}+Q_{n-2}^{11}\). We say that \(Q_n\)splits into four \((n-2)\)-dimensional subcubes \(Q_{n-2}^{00},Q_{n-2}^{01},Q_{n-2}^{10}\) and \(Q_{n-2}^{11}\) at positions i and j.
Let \(\beta \in \{0,1\}\). For every vertex \(x^{\alpha \beta }\) in \(Q_{n-2}^{\alpha \beta }\), let \(x^{\alpha \bar{\beta }}\) denote the unique neighbor of \(x^{\alpha \beta }\) in \(Q_{n-2}^{\alpha \bar{\beta }}\), and let \(x^{\bar{\alpha }\beta }\) denote the unique neighbor of \(x^{\alpha \beta }\) in \(Q_{n-2}^{\bar{\alpha }\beta }\), and let \(x^{\bar{\alpha }\bar{\beta }}\) denote the unique neighbor of \(x^{\bar{\alpha }\beta }\) in \(Q_{n-2}^{\bar{\alpha }\bar{\beta }}\). For a path \(P^{\alpha \beta }=(x_1^{\alpha \beta },\ldots ,x_l^{\alpha \beta })\) in \(Q_{n-2}^{\alpha \beta }\), we say that \(P^{\alpha '\beta '}=(x_1^{\alpha '\beta '},\ldots ,x_l^{\alpha '\beta '})\) is the corresponding path of \(P^{\alpha \beta }\) in \(Q_{n-2}^{\alpha '\beta '}\).
For any \(F\subseteq E(Q_n)\), let \(F^{\alpha }=F\cap E(Q_{n-1}^\alpha )\) and \(F^{\alpha \beta }=F\cap E(Q_{n-2}^{\alpha \beta })\).
The parityp(u) of a vertex \(u=\delta _1\cdots \delta _n\) in \(Q_n\) is defined by \(p(u)=\sum _{i=1}^n\delta _i\)(mod 2). Then there are \(2^{n-1}\) vertices with parity 0 and \(2^{n-1}\) vertices with parity 1 in \(Q_n\). Vertices with parity 0 and 1 are called black vertices and white vertices, respectively. Observe that \(Q_n\) is bipartite and vertices of each parity form bipartite sets of \(Q_n\).
We give some results which will be used in the proof of the main results.
Theorem 2.1
[19] \(Q_n\)has a Hamiltonian cycle for every\(n\ge 2\).
Theorem 2.2
[20] If\(n\ge 1\)and\(x,y\in V(Q_n)\)are such that\(p(x)\ne p(y)\), then\(Q_n\)contains a hamiltonian path joining x and y.
Lemma 2.3
[23] For \(n\ge 2\), let x, y, u be pairwise distinct vertices in \(Q_n\) with \(p(x)=p(y)\ne p(u)\). Then there exists a hamiltonian path joining x and y in \(Q_n-u\).
Lemma 2.4
[22] \(Q_n\) has a hamiltonian cycle even if it has \((n-2)\) edge faults for every \(n\ge 2\).
Lemma 2.5
[32] Assume that \(n\ge 2\) and F is a subset of edges with \(|F|\le n-2\). Then there exists a hamiltonian path in \(Q_n-F\) joining any two vertices of different colors.
Theorem 2.6
[11] Let\(n>2k\ge 4\)and\(F\subset E(Q_n)\)with\(|F|\le n-2k-1\). Assume that\(S=\{s_1,\ldots ,s_k\}\)and\(T=\{t_1,\ldots ,t_k\}\)are distinct vertices of\(Q_n\)such that\(S\cup T\)contains k vertices from each class of bipartition of\(Q_n\). Then\(Q_n-F\)have k vertex disjoint paths\(P_{s_1,t_1},\ldots ,P_{s_k,t_k}\)which cover all vertices of\(Q_n\).
3 The main results
Theorem 3.1
Let\(u,v\in V(Q_n)\)be such that\(p(u)\ne p(v)\)and let\(1\le k\le n\). Then there exists a u-to-v k-disjoint path cover\(\{P_1,P_2,\ldots ,P_k\}\)in\(Q_n\).
Proof
When \(k=1\), by Theorem 2.2, there exists a hamiltonian path joining u and v in \(Q_n\). This is a u-to-v 1-disjoint path cover in \(Q_n\).
When \(k=2\), now \(n\ge 2\). By Theorem 2.1, there is a hamiltonian cycle in \(Q_n\). Let \(P_1\) and \(P_2\) be the two paths on the cycle joining the vertices u and v. Then \(\{P_1,P_2\}\) is a u-to-v 2-disjoint path cover in \(Q_n\).
Next, we consider the case \(k\ge 3\). Now \(n\ge k\ge 3\). We prove the theorem by induction on n.
For \(n=3\), now \(k=3\). Since \(p(u)\ne p(v)\), without loss of generality, there are two cases of \(\{u,v\}\) to consider. See Fig. 2. For the two cases, we can verify that the conclusion holds.
Suppose that the theorem holds for \(n-1(\ge 3)\). We are to show that it holds for \(n(\ge 4)\).
Case 1\(d(u,v)<n\).
Since \(d(u,v)<n\), there exists a position \(j\in [n]\) such that \(u,v\in V(Q_{n-1}^0)\). Denote u by \(u^0\) and v by \(v^0\). Since \(3\le k\le n\), we have \(2\le k-1\le n-1\). By induction, there exists a u-to-v\((k-1)\)-disjoint path cover \(\{P^0_1,P^0_2,\ldots ,P^0_{k-1}\}\) in \(Q_{n-1}^0\). Since \(p(u)\ne p(v)\), we have \(p(u^1)\ne p(v^1)\). By Theorem 2.2, there exists a hamiltonian path \(P_{u^1,v^1}\) in \(Q_{n-1}^1\). Let \(P_i=P^0_i\) for every \(i\in [k-1]\), and let \(P_k=uu^1+P_{u^1,v^1}+v^1v\). Thus, \(\{P_1,P_2,\ldots ,P_k\}\) is a u-to-vk-disjoint path cover in \(Q_n\). See Fig. 3.
Case 2\(d(u,v)=n\). In this case, since \(p(u)\ne p(v)\), we have n is odd and \(n\ge 5\).
Arbitrarily split \(Q_n\) at some two positions to subcubes \(Q_{n-2}^{00}\), \(Q_{n-2}^{01}\), \(Q_{n-2}^{10}\) and \(Q_{n-2}^{11}\). Without loss of generality, we may assume \(u\in V(Q_{n-2}^{00})\). Then \(v\in V(Q_{n-2}^{11})\). Denote u by \(u^{00}\) and v by \(v^{11}\).
Since \(3\le k\le n\), we have \(1\le k-2\le n-2\). In \(Q_{n-2}^{00}\), since \(p(u)\ne p(v^{00})\), by induction, there exists a u-to-\(v^{00}\)\((k-2)\)-disjoint path cover \(\{P_1^{00},\)\(\ldots ,P_{k-2}^{00}\}\) of \(Q_{n-2}^{00}\). For every \(i\in [k-2]\), let \(P_i^{01}\) be the corresponding path of \(P_i^{00}\) in \(Q_{n-2}^{01}\), and let \(P_i^{11}\) be the corresponding path of \(P_i^{00}\) in \(Q_{n-2}^{11}\). Then \(\{P_1^{01},\)\(\ldots ,P_{k-2}^{01}\}\) is a \(u^{01}\)-to-\(v^{01}\)\((k-2)\)-disjoint path cover of \(Q_{n-2}^{01}\), and \(\{P_1^{11},\)\(\ldots ,P_{k-2}^{11}\}\) is a \(u^{11}\)-to-v\((k-2)\)-disjoint path cover of \(Q_{n-2}^{11}\). See Fig. 4.
For every \(i\in [k-2]\), let \(x_i^{01}\) and \(y_i^{01}\) be the neighbors of \(v^{01}\) and \(u^{01}\) on the path \(P_i^{01}\), respectively. Since \(d(u,v)=n\), we have \(d(v^{01},u^{01})=n-2\ge 3\). Thus \(x_i^{01}\) and \(y_i^{01}\) are distinct vertices and they are different from the vertices \(u^{01},v^{01}\). Next, we construct a u-to-vk-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) of \(Q_n\).
Step 1 Let \(P_1=P_1^{00}+v^{00}v^{01}+v^{01}v\).
Step 2 If \(k-2=1\), then skip this step. If \(k-2\ge 2\), then for every \(i\in \{2,\ldots ,k-2\}\), let \(P_i=P_i^{00}[u,x_i^{00}]+x_i^{00}x_i^{01}+P_i^{01}[x_i^{01},y_i^{01}]+y_i^{01}y_i^{11}+P_i^{11}[y_i^{11},v]\).
Step 3 Let \(P_{k-1}=uu^{01}+P_1^{01}[u^{01},x_1^{01}]+x_1^{01}x_1^{11}+x_1^{11}v\). Let \(s_1^{11}\) be the neighbor of \(x_1^{11}\) on the path \(P_1^{11}[x_1^{11},u^{11}]\). Then \(p(s_1^{11})=p(v)\ne p(u)\). So \(p(s_1^{10})=p(v^{10})\ne p(u^{10})\). By Lemma 2.3, there is a hamiltonian path \(P_{s_1^{10},v^{10}}\) in \(Q_{n-2}^{10}-u^{10}\). Let \(P_k=uu^{10}+u^{10}u^{11}+P_1^{11}[u^{11},s_1^{11}]+s_1^{11}s_1^{10}+P_{s_1^{10},v^{10}}+v^{10}v\).
Then \(\{P_1,P_2,\ldots ,P_k\}\) is a u-to-vk-disjoint path cover in \(Q_n\). \(\square \)
Theorem 3.2
Let\(u,v\in V(Q_n)\)be such that\(p(u)\ne p(v)\). Let\(F\subseteq E(Q_n)\)and\(1\le k\le n-2\). If\(|F|\le n-2-k\), then there exists a u-to-v k -disjoint path cover\(\{P_1,P_2,\ldots ,P_k\}\)in\(Q_n-F\).
Proof
If \(F=\emptyset \), then by Theorem 3.1, the theorem holds. So in the following, we only need to consider the case \(|F|\ge 1\). Now \(k\le n-3\).
When \(k=1\), now \(|F|\le n-3\). By Lemma 2.5, there exists a hamiltonian path joining vertices u and v in \(Q_n-F\). This is a u-to-v 1-disjoint path cover in \(Q_n-F\). In this case, the theorem holds.
When \(k=2\), now \(|F|\le n-4\). By Lemma 2.4, there is a hamiltonian cycle in \(Q_n-F\). Let \(P_1\) and \(P_2\) be the two paths on the cycle joining the vertices u and v. Then \(\{P_1,P_2\}\) is a u-to-v 2-disjoint path cover in \(Q_n-F\). In this case, the theorem holds.
So, we only need to consider the case \(k\ge 3\). Now \(n\ge k+3\ge 6\). We prove the theorem by induction on n.
First we prove the basis of induction. When \(n=6\), now \(k=3\) and \(|F|=1\). Let \(F=\{f\}\). Since \(p(u)\ne p(v)\), we have d(u, v) is odd. So \(d(u,v)<6\). Hence there exists a position \(j\in [6]\) such that \(u,v\in V(Q_5^0)\). Denote u by \(u^0\) and v by \(v^0\).
If \(f\in E(Q_5^0)\), then by Lemma 2.4 there is a hamiltonian cycle in \(Q_5^0-F\). Let \(P_1,P_2\) be the two paths on the cycle joining vertices u and v. Since \(p(u^1)\ne p(v^1)\), by Theorem 2.2, there is a hamiltonian path \(P_{u^1,v^1}\) in \(Q_5^1\). Let \(P_3=uu^1+P_{u^1,v^1}+v^1v\). Then \(\{P_1,P_2,P_3\}\) is a u-to-v 3-disjoint path cover in \(Q_6-F\).
If \(f\notin E(Q_5^0)\), then by Theorem 3.1 there is a u-to-v 3-disjoint path cover \(\{P_1^0,P_2^0,P_3^0\}\) in \(Q_5^0\). See Fig. 5. Since \(\sum _{i=1}^3|E(P_i^0)|=2^5-2+3>3\), there exists an edge \(x^0y^0\in E(P_i^0)\) for some \(i\in [3]\) such that \(x^0x^1\ne f\) and \(y^0y^1\ne f\). Without loss of generality, assume \(i=3\). Since \(|F|\le 1\), by Lemma 2.5, there is a hamiltonian path \(P_{x^1,y^1}\) in \(Q_5^1-F\). Let \(P_1=P_1^0\), \(P_2=P_2^0\), and \(P_3=P_3^0-x^0y^0+x^0x^1+P_{x^1,y^1}+y^1y^0\). Then \(\{P_1,P_2,P_3\}\) is a u-to-v 3-disjoint path cover in \(Q_6-F\).
By the above two cases, we know that the theorem holds for \(n=6\). Suppose that the theorem holds for \(n-1(\ge 6)\). We are to show that it holds for \(n(\ge 7)\). We distinguish two cases (Cases 1 and 2) to consider.
Case 1\(d(u,v)<n\).
Since \(d(u,v)<n\), there exists a position \(j\in [n]\) such that \(u,v\in V(Q_{n-1}^0)\). Denote u by \(u^0\) and v by \(v^0\). We distinguish two subcases (Subcases 1.1 and 1.2) to consider.
Subcase 1.1\(|F_0|\le |F|-1\).
Now \(3\le k\le n-3=(n-1)-2\), and \(|F_0|\le |F|-1\le (n-1)-2-k\). By induction, there exists a u-to-vk-disjoint path cover \(\{P^0_1,P^0_2,\ldots ,P^0_k\}\) in \(Q_{n-1}^0-F^0\). Since \(\sum _{i=1}^k|E(P_i^0)|=2^{n-1}-2+k>2k+2(|F|-2)\) for \(n\ge 7\), there exists an edge \(x^0y^0\in E(P^0_i)\) for some \(i\in [k]\) such that \(x^0x^1\notin F\) and \(y^0y^1\notin F\). Without loss of generality, we may assume \(i=k\). Since \(|F_1|\le |F|\le n-5<(n-1)-2\), by Lemma 2.5, there exists a hamiltonian path \(P_{x^1,y^1}\) in \(Q_{n-1}^1-F_1\). Let \(P_i=P^0_i\) for every \(i\in [k-1]\), and let \(P_k=P^0_k-x^0y^0+x^0x^1+P_{x^1,y^1}+y^1y^0\). Thus, \(\{P_1,P_2,\ldots ,P_k\}\) is a u-to-vk-disjoint path cover in \(Q_n-F\).
Subcase 1.2\(F_0=F\).
Since \(3\le k\le n-3\) and \(|F|\le n-2-k\), we have \(2\le k-1\le n-4<(n-1)-2\) and \(|F_0|=|F|\le (n-1)-2-(k-1)\). By induction, there exists a u-to-v\((k-1)\)-disjoint path cover \(\{P^0_1,P^0_2,\ldots ,P^0_{k-1}\}\) in \(Q_{n-1}^0-F^0\). Since \(p(u^1)\ne p(v^1)\), by Theorem 2.2, there exists a hamiltonian path \(P_{u^1,v^1}\) in \(Q_{n-1}^1\). Let \(P_i=P^0_i\) for every \(i\in [k-1]\), and let \(P_k=uu^1+P_{u^1,v^1}+v^1v\). Thus, \(\{P_1,P_2,\ldots ,P_k\}\) is a u-to-vk-disjoint path cover in \(Q_n-F\).
By the above two subcases, we know that the theorem holds for Case 1.
Case 2\(d(u,v)=n\). In this case, since \(p(u)\ne p(v)\), we have n is odd and \(n\ge 7\).
Since \(|F|\le n-2-k\le n-5\), there exist two positions \(j_1\) and \(j_2\) such that \(E_{j_1}\cap F=\emptyset \) and \(E_{j_2}\cap F=\emptyset \). Split \(Q_n\) at positions \(j_1\) and \(j_2\) to subcubes \(Q_{n-2}^{00}\), \(Q_{n-2}^{01}\), \(Q_{n-2}^{10}\), and \(Q_{n-2}^{11}\). Without loss of generality, we may assume \(u\in V(Q_{n-2}^{00})\). Then \(v\in V(Q_{n-2}^{11})\). Denote u by \(u^{00}\) and v by \(v^{11}\). Without loss of generality, we may assume \(|F^{00}|\ge |F^{11}|\). Moreover, we may assume \(|F^{01}|\ge |F^{10}|\). We distinguish two subcases (Subcases 2.1 and 2.2) to consider.
Subcase 2.1\(F^{00}=F\) or \(F^{01}=F\).
Since \(3\le k\le n-3\), we have \(1\le k-2\le n-5<(n-2)-2\).
If \(F^{00}=F\), then the other three subcubes have no faulty edges. Since \(|F^{00}|=|F|\le n-2-k=(n-2)-2-(k-2)\), by induction, there exists a u-to-\(v^{00}\)\((k-2)\)-disjoint path cover \(\{P^{00}_1,\ldots ,P^{00}_{k-2}\}\) in \(Q_{n-2}^{00}-F^{00}\). For every \(i\in [k-2]\), let \(P_i^{01}\) and \(P_i^{11}\) be the corresponding paths of \(P_i^{00}\) in \(Q_{n-2}^{01}\) and \(Q_{n-2}^{11}\), respectively. Then \(\{P_1^{01},\)\(\ldots ,P_{k-2}^{01}\}\) is a \(u^{01}\)-to-\(v^{01}\)\((k-2)\)-disjoint path cover of \(Q_{n-2}^{01}\), and \(\{P_1^{11},\)\(\ldots ,P_{k-2}^{11}\}\) is a \(u^{11}\)-to-v\((k-2)\)-disjoint path cover of \(Q_{n-2}^{11}\). See Fig. 6.
If \(F^{01}=F\), then similarly, by induction there exists a \(u^{01}\)-to-\(v^{01}\)\((k-2)\)-disjoint path cover \(\{P^{01}_1,\ldots ,P^{01}_{k-2}\}\) in \(Q_{n-2}^{01}-F^{01}\). For every \(i\in [k-2]\), let \(P_i^{00}\) and \(P_i^{11}\) be the corresponding paths of \(P_i^{01}\) in \(Q_{n-2}^{00}\) and \(Q_{n-2}^{11}\), respectively. Then \(\{P_1^{00},\)\(\ldots ,P_{k-2}^{00}\}\) is a u-to-\(v^{00}\)\((k-2)\)-disjoint path cover of \(Q_{n-2}^{00}\), and \(\{P_1^{11},\)\(\ldots ,P_{k-2}^{11}\}\) is a \(u^{11}\)-to-v\((k-2)\)-disjoint path cover of \(Q_{n-2}^{11}\).
In the above two cases, for every \(i\in [k-2]\), let \(x_i^{01}\) and \(y_i^{01}\) be the neighbors of \(v^{01}\) and \(u^{01}\) on the path \(P_i^{01}\), respectively. Since \(d(u,v)=n\), we have \(d(v^{01},u^{01})=n-2\ge 5\). Thus \(x_i^{01}\) and \(y_i^{01}\) are distinct vertices and they are different from the vertices \(u^{01},v^{01}\). Next, we construct a u-to-vk-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) in \(Q_n-F\).
Step 1 Let \(P_1=P_1^{00}+v^{00}v^{01}+v^{01}v\).
Step 2 If \(k-2=1\), then skip this step. If \(k-2\ge 2\), then for every \(i\in \{2,\ldots ,k-2\}\), let \(P_i=P_i^{00}[u,x_i^{00}]+x_i^{00}x_i^{01}+P_i^{01}[x_i^{01},y_i^{01}]+y_i^{01}y_i^{11}+P_i^{11}[y_i^{11},v]\).
Step 3 Let \(P_{k-1}=uu^{01}+P_1^{01}[u^{01},x_1^{01}]+x_1^{01}x_1^{11}+x_1^{11}v\). Let \(s_1^{11}\) be the neighbor of \(x_1^{11}\) on the path \(P_1^{11}[x_1^{11},u^{11}]\). Then \(p(s_1^{11})=p(v)\ne p(u)\). So \(p(s_1^{10})=p(v^{10})\ne p(u^{10})\). By Lemma 2.3, there is a hamiltonian path \(P_{s_1^{10},v^{10}}\) in \(Q_{n-2}^{10}-u^{10}\). Let \(P_k=uu^{10}+u^{10}u^{11}+P_1^{11}[u^{11},s_1^{11}]+s_1^{11}s_1^{10}+P_{s_1^{10},v^{10}}+v^{10}v\).
Then \(\{P_1,P_2,\ldots ,P_k\}\) is a u-to-vk-disjoint path cover in \(Q_n-F\). So in this case, the theorem holds.
Subcase 2.2\(|F^{00}|\le |F|-1\) and \(|F^{01}|\le |F|-1\).
In this case, we may observe that \(|F|\ge 2\). For the sake of discussion, we distinguish two subcases (Subcases 2.2.1 and 2.2.2) to consider.
Subcase 2.2.1\(|F^{01}|\le |F|-2\).
Since \(3\le k\le n-3\), we have \(2\le k-1\le n-4=(n-2)-2\). Since \(|F|\le n-2-k\), we have \(|F^{11}|\le |F^{00}|\le n-2-k-1=(n-2)-2-(k-1)\). By induction, there exist a u-to-\(v^{00}\)\((k-1)\)-disjoint path cover \(\{P^{00}_1,P^{00}_2,\ldots ,P^{00}_{k-1}\}\) in \(Q_{n-2}^{00}-F^{00}\) and a \(u^{11}\)-to-v\((k-1)\)-disjoint path cover \(\{P^{11}_1,P^{11}_2,\ldots ,P^{11}_{k-1}\}\) in \(Q_{n-2}^{11}-F^{11}\). (Note that in this case, \(P_i^{11}\) are not necessarily the corresponding path of \(P_i^{00}\) in \(Q_{n-2}^{11}\).) Let \(k_1=\lceil \frac{k-1}{2}\rceil \) and \(k_2=\lfloor \frac{k-1}{2}\rfloor \). Then \(k_1+k_2=k-1\).
For every \(i\in \{2,\ldots ,k-1\}\), let \(x_i^{00}\) be the neighbor of \(v^{00}\) on the path \(P_i^{00}\), and let \(y_i^{11}\) be the neighbor of \(u^{11}\) on the path \(P_i^{11}\). Since \(d(u,v)=n\ge 7\), we have \(d(u,v^{00})=d(u^{11},v)=n-2\ge 5\). So \(x_i^{00}\ne u\) and \(y_i^{11}\ne v\). Hence \(u^{01},v^{01},x_i^{01},y_i^{01},i\in \{2,\ldots ,k_1\},\) are distinct vertices, and \(p(x_i^{01})=p(u^{01})\ne p(v^{01})=p(y_i^{01})\). Similarly, we have \(u^{10},v^{10},x_t^{10},y_t^{10},t\in \{k_1+1,\ldots ,k-1\},\) are distinct vertices, and \(p(x_t^{10})=p(u^{10})\ne p(v^{10})=p(y_t^{10})\).
Note that \(k_1\ge 1\) and \(k\ge 2k_1\). Then \(|F^{01}|\le |F|-2\le n-2-k-2\le n-2-2k_1-2<(n-2)-2k_1-1\). If \(k_1=1\), then by Lemma 2.5, there is a hamiltonian path \(P_{u^{01},v^{01}}\) in \(Q_{n-2}^{01}-F^{01}\). If \(k_1\ge 2\), then by Theorem 2.6, \(Q_{n-2}^{01}-F^{01}\) have \(k_1\) vertex disjoint paths \(P_{u^{01},v^{01}},P_{x_2^{01},y_2^{01}},\)\(\ldots ,P_{x_{k_1}^{01},y_{k_1}^{01}}\) which cover all the vertices of \(Q_{n-2}^{01}\).
Similarly, \(k_2\ge 1\) and \(k\ge 2k_2+1\). Then \(|F^{10}|\le |F|-2\le n-2-k-2\le n-2-(2k_2+1)-2=(n-2)-2(k_2+1)-1\). By Theorem 2.6, \(Q_{n-2}^{10}-F^{10}\) have \(k_2+1\) vertex disjoint paths \(P_{u^{10},v^{10}},P_{x_{k_1+1}^{10},y_{k_1+1}^{10}},\)\(\ldots ,P_{x_{k-1}^{10},y_{k-1}^{10}}\) which cover all the vertices of \(Q_{n-2}^{10}\).
Next, we construct a u-to-vk-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) in \(Q_n-F\).
Step 1 Let \(P_1=P_1^{00}+v^{00}v^{01}+P_{v^{01},u^{01}}+u^{01}u^{11}+P_1^{11}\).
Step 2 If \(k_1=1\), then skip this step. If \(k_1\ge 2\), then for every \(i\in \{2,\ldots ,k_1\}\), let \(P_i=P_i^{00}[u,x_i^{00}]+x_i^{00}x_i^{01}+P_{x_i^{01},y_i^{01}}+y_i^{01}y_i^{11}+P_i^{11}[y_i^{11},v]\).
Step 3 For every \(t\in \{k_1+1,\ldots ,k-1\}\), let \(P_t=P_t^{00}[u,x_t^{00}]+x_t^{00}x_t^{10}+P_{x_t^{10},y_t^{10}}+y_t^{10}y_t^{11}+P_t^{11}[y_t^{11},v]\).
Step 4 Let \(P_k=uu^{10}+P_{u^{10},v^{10}}+v^{10}v\).
Then \(\{P_1,P_2,\ldots ,P_k\}\) is a u-to-vk-disjoint path cover in \(Q_n-F\). See Fig. 7.
Subcase 2.2.2\(|F^{01}|=|F|-1\).
Since \(2\le |F|\le n-2-k\), we have \(3\le k\le n-4\). So \(2\le k-1\le n-5<(n-2)-2\). Since \(|F^{01}|=|F|-1\), we have \(|F^{00}|+|F^{10}|+|F^{11}|=1\).
If \(|F^{00}|=1\), then \(|F^{10}|=|F^{11}|=0\). Since \(|F^{00}|=1\le (n-2)-2-(k-1)\), by induction, there exists a u-to-\(v^{00}\)\((k-1)\)-disjoint path cover \(\{P^{00}_1,P^{00}_2,\ldots ,P^{00}_{k-1}\}\) in \(Q_{n-2}^{00}-F^{00}\). For every \(i\in [k-1]\), let \(P_i^{10}\) and \(P_i^{11}\) be the corresponding paths of \(P_i^{00}\) in \(Q_{n-2}^{10}\) and \(Q_{n-2}^{11}\), respectively. Then \(\{P_1^{10},\)\(\ldots ,P_{k-2}^{10}\}\) is a \(u^{10}\)-to-\(v^{10}\)\((k-1)\)-disjoint path cover of \(Q_{n-2}^{10}\), and \(\{P_1^{11},\)\(\ldots ,P_{k-2}^{11}\}\) is a \(u^{11}\)-to-v\((k-1)\)-disjoint path cover of \(Q_{n-2}^{11}\). Similarly, if \(|F^{10}|=1\) or \(|F^{11}|=1\), then the other two subcubes have no faulty edges. Hence we may also construct the above three path covers. See Fig. 8.
For every \(i\in \{2,\ldots ,k-1\}\), let \(x_i^{10}\) and \(y_i^{10}\) be the neighbors of \(v^{10}\) and \(u^{10}\) on the path \(P_i^{10}\), respectively. Since \(d(u,v)=n\), we have \(d(v^{10},u^{10})=n-2\ge 5\). Thus \(x_i^{10}\) and \(y_i^{10}\) are distinct vertices and they are different from the vertices \(u^{10},v^{10}\). Next, we construct a u-to-vk-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) in \(Q_n-F\).
Step 1 Let \(P_1=P_1^{00}+v^{00}v^{10}+P_1^{10}+u^{10}u^{11}+P_1^{11}\).
Step 2 For every \(i\in \{2,\ldots ,k-1\}\), let \(P_i=P_i^{00}[u,x_i^{00}]+x_i^{00}x_i^{10}+P_i^{10}[x_i^{10},y_i^{10}]+y_i^{10}y_i^{11}+P_i^{11}[y_i^{11},v]\).
Step 3 Since \(|F^{01}|=|F|-1\le n-2-k-1<(n-2)-2\), by Lemma 2.5, there is a hamiltonian path \(P_{u^{01},v^{01}}\) in \(Q_{n-2}^{01}-F^{01}\). Let \(P_k=uu^{01}+P_{u^{01},v^{01}}+v^{01}v\).
Then \(\{P_1,P_2,\ldots ,P_k\}\) is a u-to-vk-disjoint path cover in \(Q_n-F\).
By the above two subcases (Subcases 2.2.1 and 2.2.2), we know that the theorem holds for Subcase 2.2.
To sum up, by the principle of the induction hypothesis, the theorem holds. \(\square \)
4 Concluding remarks
Finding node-disjoint paths is one of the most important issues in various interconnection networks, which is concerned with routing among nodes and embedding of linear arrays.
In this paper, we investigate the problem of one-to-one disjoint path cover in hypercubes with faulty edges and obtain the following results: Let \(u,v\in V(Q_n)\) be such that \(p(u)\ne p(v)\) and \(1\le k\le n\). Then there exists a one-to-one k-disjoint path cover \(\{P_1,P_2,\ldots ,P_k\}\) joining vertices u and v in \(Q_n\). Moreover, when \(1\le k\le n-2\), the result still holds even if removing \(n-2-k\) edges from \(Q_n\).
References
Arabnia HR (1990) A parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput 10(2):188–193
Arabnia HR, Bhandarkar SM (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. J Supercomput 10(3):243–270 (Special Issue on Parallel and Distributed Processing)
Arabnia HR, Taha TR (1998) A parallel numerical algorithm on a reconfigurable multi-ring network. J Telecommun Syst 10:185–203 (Special issue on Interconnections Networks)
Bhandarkar SM, Arabnia HR (1995) The Hough transform on a reconfigurable multi-ring network. J Parallel Distrib Comput 24(1):107–114
Bhandarkar SM, Arabnia HR (1995) The REFINE multiprocessor theoretical properties and algorithms. Parallel Comput 21(11):1783–1806
Bhandarkar SM, Arabnia HR (1997) Parallel computer vision on a reconfigurable multiprocessor network. IEEE Trans Parallel Distrib Syst 8(3):292–310
Bondy J, Murty U (1976) Graph theory with applications. Macmillan Press, London
Caha R, Koubek V (2007) Spanning multi-paths in hypercubes. Discret Math 307:2053–2066
Cao H, Zhang B, Zhou Z (2018) One-to-one disjoint path covers in digraphs. Theor Comput Sci 714:27–35
Castaneda N, Gotchev I (2010) Embedded paths and cycles in faulty hypercubes. J Combin Optim 20(3):224–248
Chen XB (2012) Paired many-to-many disjoint path covers of hypercubes with faulty edges. Inf Process Lett 112:61–66
Chen XB (2013) Paired many-to-many disjoint path covers of the hypercubes. Inf Sci 236(1):218–223
Cheng D, Hao R, Feng Y (2014) Two node-disjoint paths in balanced hypercubes. Appl Math Comput 242:127–142
Dimitrov D, Dvořák T, Gregor P, Skrekovski R (2009) Gray codes avoiding matchings. Discret Math Theor Comput Sci 11:123–148
Dvořák T (2005) Hamiltonian cycles with prescribed edges in hypercubes. SIAM J Discret Math 19:135–144
Dvořák T, Gregor P (2007) Hamiltonian fault-tolerance of hypercubes. Electron Notes Discret Math 29:471–477
Dvořák T, Gregor P (2008) Partitions of faulty hypercubes into paths with prescribed endvertices. SIAM J Discret Math 22(4):1448–1461
Gregor P, Dvořák T (2008) Path partitions of hypercubes. Inf Process Lett 108:402–406
Gros L (1872) Theorie du Baguenodier. Aime Vingtrinier, Lyon
Havel I (1984) On Hamiltonian circuits and spanning trees of hypercube. Cas Pest Mat 109:135–152
Jo S, Park JH, Chwa KY (2013) Paired many-to-many disjoint path covers in faulty hypercubes. Theoret Comput Sci 513:1–24
Latifi S, Zheng SQ, Bagherzadeh N (1992) Optimal ring embedding in hypercubes with faulty links. In: Proceedings of the IEEE Symposium on Fault-Tolerant Computing, pp 178–184
Lewinter M, Widulski W (1997) Hyper-Hamilton laceable and caterpillar-spannable product graphs. Comput Math Appl 34:99–104
Li XJ, Liu B, Ma MJ, Xu JM (2017) Many-to-many disjoint paths in hypercubes with faulty vertices. Discret Appl Math 217:229–242
Liu D, Li J (2010) Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes. Inf Process Lett 110(14–15):580–584
Liu JJ, Wang YL (2014) Hamiltonian cycles in hypercubes with faulty edges. Inf Sci 256:225–233
Lü HZ, Zhang HP (2014) Hyper-Hamiltonian laceability of balanced hypercubes. J Supercomput 68:302–314
Park JH (2016) Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs. Theoret Comput Sci 617:45–64
Park JH, Kim HC, Lim HS (2006) Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements. IEEE Trans Parallel Distrib Syst 17(3):227–240
Shih YK, Kao SS (2011) One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes. Theoret Comput Sci 412:4513–4530
Tsai CH (2004) Linear array and ring embeddings in conditional faulty hypercubes. Theoret Comput Sci 314:431–443
Tsai CH, Tan JM, Liang T, Hsu LH (2002) Fault tolerant Hamiltonian laceability of hypercubes. Inf Process Lett 83:301–306
Valafar H, Arabnia HR, Williams G (2004) Distributed global optimization and its development on the multiring network. Int J Neural Parallel Sci Comput 12(4):465–490
Wani MA, Arabnia HR (2003) Parallel edge-region-based segmentation algorithm targeted at reconfigurable multi-ring network. J Supercomput 25(1):43–63
Xiang Y, Stewart I, Madelaine F (2011) Node-to-node disjoint paths in \(k\)-ary \(n\)-cube with faulty edges. In: Proceedings of IEEE 17th International Conference on Parallel and Distributed Systems, pp 181–187
Zhang S, Wang S (2013) Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes. Theoret Comput Sci 491:103–118
Acknowledgements
The authors would like to express their gratitude to the anonymous reviewers for their kind suggestions on the original manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is supported by NSFC (Grant Nos. 11501282 and 11861032).
Rights and permissions
About this article
Cite this article
Wang, F., Zhao, W. One-to-one disjoint path covers in hypercubes with faulty edges. J Supercomput 75, 5583–5595 (2019). https://doi.org/10.1007/s11227-019-02817-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-019-02817-6