Hamiltonian Laceability of Hypercubes with Prescribed Linear Forest and/or Faulty Edges

1. Introduction

We mostly follow [1] for graph-theoretical terminology and notation, and follow [2] for some similar graph-theoretical operations not defined here. Denote by $N_n$ the set $\{0,1,\cdots ,n-1\}$ for a positive integer $n$.

Given a bipartite graph $G$, a linear forest in $G$ is a subgraph each component of which is a path. Let $F$ be an subset of $E(G)$ and let $L$ be a linear forest in $G-F$ such that $|E(L)|+|F|\le k$ for some non-negative integer $k$. For any two nodes $x$, $y$ in different partite sets of $G$, $\{x,y\}$ and $L$ are said to be compatible if none of the paths in $L$ has $x$ or $y$ as internal node or both of them as end nodes. Denote by $\pi [x,y]$ a path between $x$ and $y$. The graph $G$ is said to be $k$-fault-tolerant-prescribed hamiltonian laceable if $G-F$ admits a hamiltonian path $\pi [x,y]$ passing through $L$ under the condition that $\{x,y\}$ and $L$ are compatible [3]. Particularly, $G$ is said to be $k$-fault-tolerant-hamiltonian laceable if $E(L)=\mathrm{\varnothing }$ [4], and $k$-prescribed-hamiltonian laceable if $F=\mathrm{\varnothing }$, and hamiltonian laceable if $E(L)=F=\mathrm{\varnothing }$ [5].

The $n$-dimensional hypercube is one of the most attractive interconnection networks for multiprocessor systems and it is bipartite, hamiltonian, $n$-regular, node-transitive, edge-transitive and recursive [6,7]. Many real multiprocessors have taken hypercubes as underlying interconnection networks. The problem of embedding hamiltonian paths and cycles with faulty edges and/or prescribed edges in hypercubes has drawn considerable attentions (see, for example, [4, 8-18 ] and references therein).

In [4], Tsai et al. investigated fault-tolerant hamiltonian laceability of hypercubes. One of their important results can be restated as follows:

In [18], Wang and Chen studied the problem of embedding fault-free hamiltonian cycles passing through a linear forest in hypercubes with or without faulty edges and they obtained the following generalized result.

In [14], Dvořák and Gregor investigated the problem of embedding hamiltonian paths passing through prescribed linear forests in hypercubes. One of their main results can be restated as follows:

In this note, we will generalize Theorems 1 and 2, and prove that $Q_n$ with $n\ge 2$ is $(n-2)$-fault-tolerant-prescribed hamiltonian laceable but not $(n-1)$-fault-tolerant-prescribed hamiltonian laceable.

2. Preliminaries

The $n$-dimensional hypercube $Q_n$ is a simple graph consists of $2^n$ nodes, each of which is an $n$-bit binary string with the form ${\delta }_0{\delta }_1\dots {\delta }_{n-1}$. Two nodes are adjacent if and only if they differ in exactly one bit. An edge $(u,v)\in E(Q_n)$ is called an edge in dimension $i$ if $u$ and $v$ differ in the $i^{th}$ bit, where $i\in N_n$. A node in $Q_n$ is called an odd node (resp. even node) if the sum of all digits of the node is odd (resp. even). Let $X$ and $Y$ be the set of all odd nodes and all even nodes in $Q_n$, respectively. Then $(X,Y)$ is a bipartition of $Q_n$. Fix $n\ge 2$. Let $F\subset E(Q_n)$ and let $L$ be a linear forest in $Q_n-F$. There are $n$ different ways to decompose $Q_n$ into two disjoint copies, $Q[0]$ and $Q[1]$, of $Q_{n-1}$ by deleting all the edges in dimension $i$ of $Q_n$ for an arbitrary $i\in N_n$, where each node of $Q[i]$ has $j$ in the $i^{th}$ bit for $j\in N_2$. For any $j\in N_2$, abbreviated $V(Q[j])$ as $V_j$, and denote by $L_j$ and $F_j$ the restrictions of $L$ and $F$ in $Q[j]$, respectively. For an arbitrary node $u\in V_j$, there is exactly one neighbour of $u$ in $Q[1-j]$, and we denote it by $u^{1-j}$.

The following two lemmas will be used in the proof of our main result in Section 3.

Proof of Lemma 1. There are $|E(P)\setminus E(L_j)|=2^{n-1}-1-|E(L_j)|$ edge candidates in total. Note that each component of a linear forest is a path. Let $(u,v)\in E(P)\setminus E(L_j)$. Then it fails the lemma only if

$(1)$. $u^{1-j}$ or $v^{1-j}$ is an internal node of $L_{1-j}$, or

$(2)$. $u^{1-j}$ and $v^{1-j}$ are the two end nodes of some component of $L_{1-j}$.

Let $y$ be an internal node of $L_{1-j}$, if any. Then it makes at most one candidate in $E(P)\setminus E(L_j)$ fail if $y^j$ is an end node of $P$, and at most two candidates fail otherwise (see, for example, in Figure 1, an internal node $y$ of the path $⟨x,y,z⟩$, a component of $L_{1-j}$, makes $(s,y^j)$ and $(t,y^j)$ fail if $(x^j,z^j)\in E(P)\setminus E(L_j)$). Note that each component of $L_{1-j}$ is a path. Let $\pi [x,z]$ be a component of $L_{1-j}$ of length at least 1. Then such a pair $\{x,z\}$ makes no candidate in $E(P)\setminus E(L_j)$ fail if $x^j$ is not adjacent to $z^j$ in $P$, and makes at most one candidate $(x^j,z^j)$ fail otherwise (see, for example, in Figure 1, the pair $\{x,z\}$ of the end nodes of a component of $L_{1-j}$ makes $(x^j,z^j)$ fail if $(x^j,z^j)\in E(P)\setminus E(L_j)$).

Note that $E(L_{j-1})\ne \mathrm{\varnothing }$. Let $m$ be the number of components of length at least 1 in $L_{j-1}$, and let $P_1$, $P_2$, …, $P_m$ be the $m$ components. Then $m\ge 1$ and the number of internal nodes of $L_{1-j}$ is $\sum _{i=1}^m(|E(P_i)|-1)=|E(L_{1-j})|-m$. Thus, the total number of edge candidates that fail the lemma does not exceed $m+2(|E(L_{1-j})|-m)=2|E(L_{1-j})|-m$. Since $|E(P)\setminus E(L_j)|-(2|E(L_{1-j})|-m)=2^{n-1}-1-|E(L_j)|-2|E(L_{1-j})|+m=2^{n-1}-1-|E(L)|-|E(L_{1-j})|+m\ge 2^{n-1}-|E(L)|-|E(L_{j-1})|>0$, the lemma follows.

Proof of Lemma 2. There are $|V_0\cap Y|$ node candidates in total. Let $u\in V_0\cap Y$. Then it fails the lemma only if

$(1)$. $u$ is an internal node of $L_j$, or

$(2)$. $u^{1-j}$ is an internal node of $L_{1-j}$, or

$(3)$. $x$ and $u$ are the two end nodes of some component of $L_j$, or

$(4)$. $y$ and $u^{1-j}$ are the two end nodes of some component of $L_{1-j}$.

If $E(L_j)=\mathrm{\varnothing }$, then there is no $u\in V_0\cap Y$ such that $(1)$ or $(3)$ hold. If $E(L_j)\ne \mathrm{\varnothing }$, then the number of internal nodes of $L_j$ does not exceed $|E(L_j)|-1$ and the number of such $u$ that $(3)$ holds does not exceed $1$. Therefore, the total number of such a node $u$ that $(1)$ or $(3)$ hold does not exceed $|E(L_j)|$. Similarly, the total number of such a node $u$ that $(2)$ or $(4)$ hold does not exceed $|E(L_{1-j})|$. Therefore, the number of such a node $u$ that fails the lemma does not exceed $|E(L_j)|+|E(L_{1-j})|$. Since $|V_0\cap Y|-(|E(L_j)|+|E(L_{1-j})|)=2^{n-2}-(|E(L_j)|+|E(L_{1-j})|)>0$, the lemma follows.

3. Main Result

Proof of Theorem 4. By Theorem 1, $Q_n$ with $n\ge 2$ is not $(n-1)$-fault-tolerant hamiltonian laceable, and so it is not $(n-1)$-fault-tolerant-prescribed hamiltonian laceable. It remains to prove that $Q_n$ is $(n-2)$-fault-tolerant hamiltonian laceable for $n\ge 2$. Let $F\subset E(Q_n)$ and let $L$ be a linear forest in $Q_n-F$ such that $|E(L)|+|F|\le n-2$. Let $x\in X$ and $y\in Y$ such that $\{x,y\}$ and $L$ are compatible. In the following, it is enough to prove that $Q_n-F$ admits a hamiltonian path $\pi [x,y]$ passing through $L$, and it suffices to consider the case that $|E(L)|+|F|=n-2$.

We will prove the above statement by induction on $n$. It is trivial for the base case $n=2$. For $n=3$, $|E(L)|+|F|\le 1$, Theorems 1 and 3 imply that the statement holds. In the remainder, assume that the statement holds for $Q_{n-1}$ and prove that it also holds for $Q_n$, where $n\ge 4$. By Theorems 1 and 3, the statement holds for $E(L)=\mathrm{\varnothing }$ or $F=\mathrm{\varnothing }$, respectively. It remains to show that it also holds for $E(L)\ne \mathrm{\varnothing }$ and $F\ne \mathrm{\varnothing }$. Since $|E(L)|+|F|=n-2<n$, there is a dimension, say dimension 0, such that there is no edge of $E(L)\cup F$ in this dimension. Let $Q[0]$, $Q[1]$ be a decomposition of $Q_n$ by deleting all the edges in dimension 0. Without loss of generality, assume that $|E(L_0)|+|F_0|\ge |E(L_1)|+|F_1|$. There are three cases to be considered.

Case 1. $x\in V_0$ and $y\in V_0$.

Suppose first that $|E(L_0)|+|F_0|=n-2$. Then $L_0=L$, $F_0=F$ and $E(L_1)=F_1=\mathrm{\varnothing }$. Let $f\in F_0$. Then $|E(L_0)\cup F_0\setminus \{f\}|=n-3$. By the induction hypothesis, $Q[0]-F_0\setminus \{f\}$ has a hamiltonian path $\pi [x,y]$ passing through $L_0$. Let $(u,v)=f$ if $f$ lies on $\pi [x,y]$, and let $(u,v)$ be an arbitrary edge in $E(\pi [x,y])\setminus E(L_0)$ otherwise. Clearly, $u^1$ and $v^1$ lie in different partite sets of $Q[1]$, and so $Q[1]$ has a hamiltonian path $\pi [u^1,v^1]$.

Suppose now that $|E(L_0)|+|F_0|\le n-3$. By the induction hypothesis, $Q[0]-F_0$ has a hamiltonian path $\pi [x,y]$ passing through $L_0$. Note that $|F|\ge 1$ and $|E(L_1)|\le |E(L)|<|E(L)|+|F|=n-2$. Then $2^{n-1}-|E(L)|-|E(L_1)|>2^{n-1}-2(n-2)>0$, and so Lemma 1 implies that there exists an edge $(u,v)\in E(\pi [x,y])\setminus E(L_0)$ such that $\{u^1,v^1\}$ and $L_1$ are compatible. Since $|E(L_1)|+|F_1|\le |E(L_0)|+|F_0|\le n-3$, by the induction hypothesis, $Q[1]-F_1$ has a hamiltonian path $\pi [u^1,v^1]$ passing through $L_1$.

For all the possible scenarios above, $\pi [x,y]\cup \pi [u^1,v^1]+\{(u,u^1),(v,v^1)\}-(u,v)$ is a hamiltonian path of $Q_n-F$ between $x$ and $y$ passing through $L$ as illustrated in Figure 2 (a).

Case 2. $x\in V_1$ and $y\in V_1$.

Case 2.1. $|E(L_0)|+|F_0|=n-2$.

In this case, $|F_0|=|F|\ge 1$, $1\le |E(L_0)|=|E(L)|\le n-3$, and $E(L_1)=F_1=\mathrm{\varnothing }$. Theorem 2 implies that $Q[0]-F_0$ has a hamiltonian cycle $C_0$ passing through $L_0$. Since $|E(C_0)\setminus E(L_0)|=|E(C_0)|-|E(L_0)|\ge 2^{n-1}-(n-3)>1$, there exists an edge $(u,v)\in E(C)\setminus E(L_0)$ such that $\{u^1,v^1\}\ne \{x,y\}$. Thus, $\{x,y\}$ and the path $⟨u^1,v^1⟩$ are compatible. Combing this with $|\{(u^1,v^1)\}|=1\le n-3$ ($n\ge 4$), by Theorem 3, $Q[1]-F_1$ has a hamiltonian path $\pi [x,y]$ passing through $⟨u^1,v^1⟩$. Thus, $C_0\cup \pi [x,y]+\{(u,u^1),(v,v^1)\}-\{(u,v),(u^1,v^1)\}$ is a hamiltonian path of $Q_n-F$ between $x$ and $y$ passing through $L$ as illustrated in Figure 2 (b).

Case 2.2. $|E(L_0)|+|F_0|\le n-3$.

Note that $|E(L_1)|+|F_1|\le |E(L_0)|+|F_0|\le n-3$. By the induction hypothesis, $Q[1]-F_1$ has a hamiltonian path $\pi [x,y]$ passing through $L_1$. Since $2^{n-1}-|E(L)|-|E(L_0)|>2^{n-1}-2(n-2)>0$, Lemma 1 implies that there exists an edge $(u,v)\in E(\pi [x,y])\setminus E(L_1)$ such that $\{u^0,v^0\}$ and $L_0$ are compatible. Since $|E(L_0)|+|F_0|\le n-3$, by the induction hypothesis, $Q[0]-F_0$ has a hamiltonian path $\pi [u^0,v^0]$ passing through $L_0$. Thus, $\pi [u^0,v^0]\cup \pi [x,y]+\{(u^0,u),(v^0,v)\}-(u,v)$ is a hamiltonian path of $Q_n-F$ between $x$ and $y$ passing through $L$ as illustrated in Figure 2 (c).

Case 3. $x\in V_0$ and $y\in V_1$, or $y\in V_0$ and $x\in V_1$.

Without loss of generality, assume that $x\in V_0$ and $y\in V_1$.

Case 3.1. $|E(L_0)|+|F_0|=n-2$.

In this case, $E(L_1)=F_1=\mathrm{\varnothing }$. Theorem 2 implies that $Q[0]-F_0$ has a hamiltonian cycle $C_0$ passing through $L_0$. Since $\{x,y\}$ and $L$ are compatible, $x$ is not an internal node in $L$, and so there is a neighbour $u$ of $x$ on $C_0$ such that $(x,u)\notin E(L_0)$. Recall that $x$ is an odd node and $y$ is an even node. Then $u$ is an even node and $u^1$ is an odd node. Thus, $u^1$ and $y$ are in different partite sets of $Q[1]$, and so there is a hamiltonian path $\pi [u^1,y]$ in $Q[1]$. Therefore, $C_0\cup \pi [u^1,y]+(u,u^1)-(x,u)$ is a hamiltonian path of $Q_n-F$ between $x$ and $y$ passing through $L$ as illustrated in Figure 3 (a).

Case 3.2. $|E(L_0)|+|F_0|\le n-3$.

Since $2^{n-2}-(|E(L_0)|+|E(L_1)|)=2^{n-2}-|E(L)|\ge 2^{n-2}-(n-3)>0$, Lemma 2 implies that there exists a node $u\in V_0\cap Y$ such that $\{x,u\}$ and $L_0$ are compatible and $\{y,u^1\}$ and $L_1$ are compatible. Since $|E(L_1)|+|F_1|\le |E(L_0)|+|F_0|\le n-3$, by the induction hypothesis, $Q[0]-F_0$ has a hamiltonian path $\pi [x,u]$ passing through $L_0$, and $Q[1]-F_1$ has a hamiltonian path $\pi [y,u^1]$ passing through $L_1$. Thus, $\pi [x,u]\cup \pi [y,u^1]+(u,u^1)$ is a hamiltonian path of $Q_n-F$ between $x$ and $y$ passing through $L$ as illustrated in Figure 3 (b).

4. Conclusion

In this note, we investigated the fault-tolerant prescribed hamiltonian laceability of hypercubes and proved that the hypercube $Q_n$ with $n\ge 2$ is $(n-2)$-fault-tolerant-prescribed hamiltonian laceable but not $(n-1)$-fault-tolerant-prescribed hamiltonian laceable. That is to say, given an arbitrary set $F\subset E(Q_n)$ and a linear forest $L$ in $Q_n$ with $n\ge 2$ such that $|F|+|E(L)|\le n-2$, for two nodes $x$ and $y$ of different partite sets in $Q_n$, $Q_n-F$ has a hamiltonian path between $x$ and $y$ passing through $L$ if $\{u,v\}$ and $L$ are compatible. Since $Q_n$ is $n$-regular, the upper bound $n-2$ on $|E(L)|+|F|$ cannot be improved. The main result in this note generalized some known results.

Acknowledgments

We would thank the anonymous reviewers for their useful suggestions and comments that improved the quality of this paper.