$(n−2)$-fault-tolerant edge-pancyclicity of möbius cubes $MQ_n$

Zhang, Huifeng; Zhu, Jun; Xu, Xirong; Zhang, Peng

doi:10.61091/ars161-03

Abstract

References

Ars Combinatoria

Volume 161
Pages: 29-47

Research article

$(n - 2)$ -fault-tolerant edge-pancyclicity of möbius cubes $M Q_{n}$

^¹,², ^¹, ^¹, ^³

¹Zhejiang Lab, Hangzhou,311100,China

²School of Computer Science and Technology Dalian University of Technology, Dalian, 116024, China

³Department of Computer Science Zhongshan College of Dalian Medical University, Dalian, 116085, China

Received: 10/01/2020
Accepted: 15/05/2020
Published: 31/12/2024

Copyright Link
License

Abstract

The $n$ -dimensional Möbius cube $M Q_{n}$ is an important variant of the hypercube $Q_{n}$ , which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of $M Q_{n}$ , and shows that if $M Q_{n}$ ( $n \geq 5$ ) contains at most $n - 2$ faulty vertices and/or edges then, for any fault-free edge $u v$ in $M Q_{n}^{i} (i = 0, 1)$ and any integer $ℓ$ with $7 - i ⩽ ℓ ⩽ 2^{n} - f_{v}$ , there is a fault-free cycle of length $ℓ$ containing the edge $u v$ , where $f_{v}$ is the number of faulty vertices. The result is optimal in some senses.

Keywords: Combinatorics, Möbius cube, Edge-pancyclicity, Fault-tolerant, Interconnection network

1. Introduction

It is well known that interconnection networks are of interest in parallel and distributed computing systems because they determine the performance of the systems on a large scale. As topological structures, interconnection networks can be represented by a graph $G = (V, E)$ , where $V$ is the vertex-set of $G$ and $E$ is the edge-set of $G$ . $| V (G) |$ and $| E (G) |$ denote the numbers of vertices and edges of $G$ , respectively. A path denoted by $(v_{1}, v_{2}, \dots, v_{k})$ is a sequence of vertices where two consecutive vertices are adjacent in $G$ . A cycle is a path $(v_{1}, v_{2}, \dots, v_{k})$ where $v_{1} = v_{k}$ . A graph $G$ is pancyclic if, for every $g i r t h ⩽ ℓ ⩽ | V (G) |$ , $G$ has a cycle of length $ℓ$ . A graph $G$ is edge-pancyclic if, for any edge $e$ of $G$ and every $g i r t h ⩽ ℓ ⩽ | V (G) |$ , $G$ has a cycle of length $ℓ$ containing $e$ . A graph $G$ is vertex-pancyclic if, for any vertex $u$ of $G$ and every $g i r t h ⩽ ℓ ⩽ | V (G) |$ , $G$ has a cycle of length $ℓ$ containing $u$ . Obviously, if a graph is edge-pancyclic, it is also vertex-pancyclic. Edge-pancyclic and vertex-pancyclic on various interconnection networks were studied, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, augmented cubes, star graphs, and others.

Edge and/or vertex failures are inevitable when a large parallel and distributed computer system is running. Thus, the fault-tolerant capacity of network is an important issue for parallel and distributed computing. A graph $G$ is $k$ -fault-tolerant pancyclic(resp., vertex-pancyclic, edge-pancyclic) if $G - F$ is still pancyclic(resp., vertex-pancyclic, edge-pancyclic) for any $F \subset E (G) \cup V (G)$ with $| F | ⩽ k$ . Pancyclicity and fault-tolerant pancyclicity have been widely studied for many well-known networks, see Xu and Ma [14] for a detail survey on these topics.

The Möbius cube has many properties superior to the hypercube. Though both the Möbius cubes and the ordinary hypercube have the same number of vertices and the same vertex degree, the diameter of the Möbius cube is approximately half that of the ordinary hypercube. Due to nearly half the diameter and better graph embedding capability as compared with its hypercube counterpart of the same size, the Mö¡§bius cubes have been proposed as promising candidates for interconnection topology, and have received considerable attention [1,2,3,6,7,8,11,13,5,4].

With regard to the fault-tolerant Hamiltonicity of Möbius cubes, Huang et al. [7] showed that an $n$ -dimensional Möbius cube is Hamiltonian in the presence of up to $n - 2$ node and edge faults. As concerns the pancyclicity and fault-tolerant pancyclicity of Möbius cubes, Fan [3] proved that Möbius cubes are four-pancyclic. Hsieh and Chen [6] found that an $n$ -dimensional Möbius cube with up to $n - 2$ edge faults is four-pancyclic.

This paper investigates the fault-tolerant edge-pancyclicity of $M Q_{n}$ , and shows that if $M Q_{n}$ ( $n \geq 5$ ) contains at most $n - 2$ faulty vertices and/or edges then, for any fault-free edge $u v$ in $M Q_{n}^{i} (i = 0, 1)$ and any integer $ℓ$ with $7 - i ⩽ ℓ ⩽ 2^{n} - f_{v}$ , there is a fault-free cycle of length $ℓ$ containing the edge $u v$ , where $f_{v}$ is the number of faulty vertices.

The remainder of this paper is organized as follows. In Section 2, we recall the definition of $M Q_{n}$ , and introduce some properties of $M Q_{n}$ to be used in our proofs. In Section 3, we give the proof of our result. Finally, we give some concluding remarks in Section 4.

2. Definitions and properties

The $n$ -dimensional Möbius cube, denoted by $M Q_{n}$ , is such an undirected graph, its vertex set is the same as the vertex set of $Q_{n}$ , the vertex $X = x_{1} x_{2} \dots x_{n}$ connects to $n$ other vertices $Y_{i}$ , ( $1 \leq i \leq n$ ), where each $Y_{i}$ satisfies one of the following equations: $Y_{i} = {\begin{cases} x_{1} x_{2} \dots x_{i - 1} {\bar{x}}_{i} x_{i + 1} \dots x_{n} & w h e n x_{i - 1} = 0, \\ x_{1} x_{2} \dots x_{i - 1} {\bar{x}}_{i} {\bar{x}}_{i + 1} \dots {\bar{x}}_{n} & w h e n x_{i - 1} = 1. \end{cases}$

From the above definition, $X$ connects to $Y_{i}$ by complementing the bit $x_{i}$ if $x_{i - 1} = 0$ or by complementing all bits of $x_{i}, \dots, x_{n}$ if $x_{i - 1} = 1$ . The connection between $X$ and $Y_{1}$ is undefined, so we can assume that $x_{0}$ is either equal to $0$ or equal to $1$ , which gives us slightly different network topologies. If we assume $x_{0} = 0$ , we call the network a ¡®0-Möbius cube¡¯; and if we assume $x_{0} = 1$ , we call the network a ¡®1-Möbius cube¡¯, denoted by $M Q_{n}^{0}$ and $M Q_{n}^{1}$ , respectively. The graphs shown in Fig.1 are $M Q_{4}^{0}$ and $M Q_{4}^{1}$ , respectivily.

According to the above definition, it is not difficult to see that $M Q_{n}^{0}$ (respectively, $M Q_{n}^{1}$ ) can be recursively constructed from $M Q_{n - 1}^{0}$ and $M Q_{n - 1}^{1}$ by adding $2^{n - 1}$ edges. $M Q_{n}^{0}$ is constructed by connecting all pairs of vertices that differ only in the $1$ -th bit, and $M Q_{n}^{1}$ is constructed by connecting all pairs of vertices that differ in the $1$ -th through the $n$ -th bits. The superscript $i$ of notation $M Q_{n}^{i}$ , $i = 0, 1$ , can be omitted if there is no ambiguity arise.

For convenience, we say that $M Q_{n - 1}^{0}$ and $M Q_{n - 1}^{1}$ are two sub-Möbius cubes of $M Q_{n}$ , where $M Q_{n - 1}^{0}$ (respectively, $M Q_{n - 1}^{1}$ ) is an ( $n - 1$ )-dimensional $0$ -Möbius cube (respectively, $1$ -Möbius cube) which includes all vertices $0 x_{2} \dots x_{n}$ (respectively, $1 x_{2} \dots x_{n}$ ), $x_{i} \in {0, 1}$ . More simply, let $L = M Q_{n - 1}^{0}$ and $R = M Q_{n - 1}^{1}$ . In addition, we define the set of crossing edges of $M Q_{n}$ to be $E_{C} = {x y \in E (M Q_{n}) | x \in V (M Q_{n - 1}^{0}) \land y \in V (M Q_{n - 1}^{1})}$ . For any edge $x y \in E_{C}$ , vertices $x$ and $y$ are crossing vertices of each other. Indeed, there are $2^{n - 1}$ crossing edges and $2^{n - 1}$ pairs of crossing vertices in $M Q_{n}$ .

The Möbius cube $M Q_{n}$ was first proposed by Cull and Larson [1]. Like $Q_{n}$ , $M Q_{n}$ is an $n$ -regular $n$ -connected graph with $2^{n}$ vertices and $n 2^{n - 1}$ edges. Moreover, $M Q_{n}$ has a diameter of $⌈ \frac{(n + 2)}{2} ⌉$ for $M Q_{n - 1}^{0}$ and $⌈ \frac{(n + 1)}{2} ⌉$ for $M Q_{n - 1}^{1}$ . However, for $n \geq 4$ , $M Q_{n}$ is neither vertex-transitive nor edge-transitive.

Cull and Larson[1] first proved the existence of hamiltonian cycles in $M Q_{n}$ by proving that in $M Q_{n}^{0}$ or $M Q_{n}^{1}$ , there are $2^{n - k}$ disjoint cycles of length $2^{k}$ for any $k \geq 2$ .

Figure 1 (a) $M Q_{4}^{0}$ , (b) $M Q_{4}^{1}$

We need the following two definitions.

Definition 2.1. For any edge $e = (x_{1} x_{2} \dots x_{n}, y_{1} y_{2} \dots y_{n}) \in E (M Q_{n})$ , let $λ (e)$ be the smallest positive integer $i \in {1, 2, \dots, n}$ such that $x_{i} \neq y_{i}$ , then $e$ is called a $λ$ -dimensional edge.

According to Definition 2.1, if we use $u_{L}$ to denote a vertex in $L$ , then $u_{R}$ always denotes its unique neighbor in $R$ , that is, $u_{L} u_{R}$ is an $1$ -dimensional edge. Let $e = u v$ be a $i_{1}$ -dimensional edge, then denote $v = u^{i_{1}}$ . Let $u^{i_{1}, \dots, i_{j - 1}, i_{j}} = {(u^{i_{1}, \dots, i_{j - 1}})}^{i_{j}}$ for $j \geq 2$ . Let $P^{t - 1} (u_{0}) = (u_{0}, u_{1}, \dots u_{j} \dots u_{t - 1})$ be a path of length $ℓ = t - 1$ , then $u_{j} = u_{j - 1}^{i_{j}}$ for $1 \leq j \leq t - 1$ . We use $(i_{1}, i_{2}, \dots, i_{t - 1})$ to denote $P^{t - 1} (u_{0})$ for short. If $u_{0} u_{t - 1} \in E$ , then we use $(i_{1}, i_{2}, \dots, i_{t - 1})$ to denote cycle $C^{t} (u_{0})$ of length $ℓ = t$ containing edge $u_{0} u_{t - 1}$ for short.

For example, for $C^{7} (000001) = (000001, 001001, 011001, 010110, 110110, 101001, 100001)$ in $M Q_{n}^{0}$ , we use $(3, 2, 3, 1, 2, 3)$ to denote the cycle $C^{7} (000001)$ .

Definition 2.2.

If $| F | = n - 2$ and there exists a vertex $w$ with $N_{M Q_{n} - F} (w) = {w_{1}, w_{2}}$ , then $w$ is called a weak 2-degree vertex and ${w_{1}, w_{2}}$ is called a $w$ -weak vertex pair(or a weak vertex pair, for short).

Since there is no triangle in $M Q_{n}$ , we can obtain the Proposition 2.3 as follows.

Proposition 2.3.

If $x y \in E (M Q_{n})$ , then $(x, y)$ is not a weak vertex-pair in $M Q_{n} - F$ with $| F | \leq n - 2$ .

Lemma 2.4.

( Xu et al. [9]) If for any vertex $u_{L} \in L$ ( $u_{R} \in R$ ), $v_{L}$ ( $v_{R}$ ) is a neighbor of $u_{L}$ ( $u_{R}$ ) in $L$ ( $R$ ) then, the distance between $u_{R}$ ( $u_{L}$ ) and $v_{R}$ ( $v_{L}$ ) is 1 or 2.

Lemma 2.5.

( Xu et al. [11]) $M Q_{n}$ is edge-pancyclic for $n \geq 2$ .

Lemma 2.6.

( Xu et al. [10]) For any two different vertices $x$ and $y$ with distance $d$ in $M Q_{n}$ $(n \geq 3)$ , there exists an $x y$ -path of every length $ℓ$ from $d$ to $2^{n} - 1$ except for $d + 1$ .

Let $F$ be a set of faulty elements in $M Q_{n}$ . We need the following lemmas:

Lemma 2.7. If any edge $u_{L} u_{R} \in E_{C}$ in $M Q_{n}^{0} - F$ for $| F | \leq n - 2$ , there exists a fault-free $4$ -cycle or $5$ -cycle containing the edge $u_{L} u_{R}$ .

Proof. Let $u_{L} = 0 x_{2} \dots x_{n}$ , we show the lemma according to the following two cases.

Case 1. $x_{2} = 0$ .

We can find ( $n - 2$ ) disjoint $4$ -cycles and a $5$ -cycle except the common edge $u_{L} u_{R}$ as follows. $\begin{array}{llll} {\begin{cases} (i + 2, & 1, & i + 2), & 1 \leq i \leq n - 2, \\ (2, & 1, & 3, & 2), i = n - 1. \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $4$ -cycle or $5$ -cycle containing the edge $u_{L} u_{R}$ . The lemma holds.

Case 2. $x_{2} = 1$ .

There exist at most $n - 2$ disjoint $4$ -cycles as $C_{i}^{4} (u_{L}) = (i, 1, i) = (u_{L}, u_{L}^{i}, u_{L}^{i, 1}, u_{R})$ for $3 \leq i \leq n$ except the common edge $u_{L} u_{R}$ .

If one of $4$ -cycle $C_{i}^{4} (u_{L})$ ( $3 \leq i \leq n$ ) is fault-free, the lemma holds.

If each $4$ -cycles $C_{i}^{4} (u_{L})$ ( $3 \leq i \leq n$ ) contains a faulty vertices. Consider $4$ -cycles $(3, 1, 3) = (u_{L}, u_{L}^{3}, u_{L}^{3, 1}, u_{R})$ .

If $u_{L}^{3, 1} \in F$ , then $u_{L}^{3} \notin F$ . We can find a fault free $5$ -cycle $(3, 2, 1, 2) = (u_{L}, u_{L}^{3}, u_{L}^{3, 2}, u_{L}^{3, 2, 1}, u_{R})$ containing the edge $u_{L} u_{R}$ .
If $u_{L}^{3} \in F$ , then $u_{L}^{3, 1} \notin F$ . We can find a fault-free $5$ -cycle $(2, 1, 2, 3) = (u_{L}, u_{L}^{2}, u_{L}^{2, 1}, u_{L}^{3, 1}, u_{R})$ containing the edge $u_{L} u_{R}$ .

The proof is completed.

Lemma 2.8. If any edge $u_{L} u_{R} \in E_{C}$ in $M Q_{n}^{1} - F$ for $| F | \leq n - 2$ , there exists a fault-free $5$ -cycle containing the edge $u_{L} u_{R}$ .

Proof. Let $u_{L} = x_{1} x_{2} \dots x_{i} x_{i + 1} \dots x_{n}$ . There exist ( $n - 2$ ) disjoint $5$ -cycles and a $4$ -cycle except the common edge $u_{L} u_{R}$ as follows. $\begin{array}{llll} {\begin{cases} (i + 1, & i + 2, & 1, & i + 1), 1 \leq i \leq n - 2 \land x_{i + 1} = 0, \\ (i + 1, & 1, & i + 2, & i + 1), 1 \leq i \leq n - 2 \land x_{i + 1} = 1, \\ (n, & 1, & n), & i = n - 1. \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $4$ -cycle or $5$ -cycle containing the edge $u_{L} u_{R}$ .

By Lemma 2.7 and 2.8, we can obtain the following result.

Corollary 2.9.

If any edge $u_{L} u_{R} \in E_{C}$ in $M Q_{n} - F$ for $| F | \leq n - 2$ , there exists a fault-free $4$ -cycle or $5$ -cycle containing the edge $u_{L} u_{R}$ .

Lemma 2.10.

(Xu et al. [9]) If $| F | \leq n - 3$ and $n \geq 3$ then, for any fault-free edge $e$ in $M Q_{n}$ and any integer $ℓ$ with $6 \leq ℓ \leq 2^{n} - f_{v}$ , there is a fault-free cycle of length $ℓ$ containing the edge $e$ in $M Q_{n}$ .

Lemma 2.11.

(Xu et al. [12]) If $F \subset V (M Q_{n}) \cup E (M Q_{n})$ and $| F | \leq n - 2$ , then for any two distinct fault-free vertices $u$ and $v$ , there exists a fault-free path $P_{u v}$ of every length $ℓ$ with $2^{n - 1} - 1 \leq ℓ \leq 2^{n} - f_{v} - 1 - α$ , where $α = 0$ if vertices $u$ and $v$ is not a weak vertex-pair in $M Q_{n} - F$ and $α = 1$ if vertices $u$ and $v$ form a weak vertex-pair in $M Q_{n} - F$ ( $n \geq 5$ ).

Figure 2 Four disjoint $6$ -cycles in $L$ except the common edge $(001011, 001100)$

Lemma 2.12.

If $F \subset V (M Q_{n}^{1})$ with $| F | \leq n - 2$ ( $n \geq 6$ ), then for any edge $u_{L} v_{L} \in L$ , there exists a fault-free $6$ -cycle containing the edge $u_{L} v_{L}$ in $M Q_{n}^{1} - F$ .

Proof. By Lemma 2.10, the lemma holds for $| F | \leq n - 3$ . We only need to consider the case of $| F | = n - 2$ .

Let $u_{L} = x_{1} x_{2} \dots x_{j} \dots x_{n}$ . We can assume that $| F_{R} | \leq | F_{L} |$ . Otherwise, if $| F_{L} | \leq | F_{R} |$ , then $| F_{L} | \leq ⌊ \frac{n - 2}{2} ⌋ \leq n - 4 (n \geq 6)$ . By Lemma 2.10, there exists a fault-free $6$ -cycle containing the edge $u_{L} v_{L}$ in $L - F_{L}$ , and so in $M Q_{n}^{1} - F$ .

If $| F_{L} | \leq n - 4$ , by Lemma 2.10 , there exists a fault-free $6$ -cycle containing the edge $u_{L} v_{L}$ .

If $| F_{L} | \geq n - 3$ , then $| F_{R} | \leq 1$ . We can prove the result according to the relationship between the $v_{L}$ and $u_{L}$ as follows.

Case 1. $v_{L} = u_{L}^{j}$ ( $j = 2$ ).

There exist $n - 1$ disjoint $6$ -cycles as $C_{i}^{6} (u_{L}) (1 \leq i \leq n - 1)$ except the common edge $u_{L} v_{L}$ as follows. $\begin{array}{llll} C_{i}^{6} (u_{L}) = {\begin{cases} (1, & 3, & 1, & 2, & 3), & i = 1, \\ (i + 1, & 2, & 1, & 3, & 1), & i = 2, \\ (i + 1, & 5, & 2, & 5, & 4), & i = 3, \\ (i + 1, & n, & 2, & n, & i + 1), & 4 \leq i \leq n - 2 \land x_{4} = 0, \\ (i + 1, & 4, & 2, & 4, & i + 1), & 4 \leq i \leq n - 2 \land x_{4} = 1, \\ (i + 1, & 4, & 2, & 4, & n), & i = n - 1. \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $6$ -cycle containing the edge $u_{L} v_{L}$ .

Case 2. $v_{L} = u_{L}^{j}$ ( $3 \leq j \leq n$ ).

Case 2.1. $u_{R}, v_{R} \notin F$ .

For $3 \leq j \leq n - 2$ , there exist two disjoint $u_{R} v_{R}$ -paths as $P_{i}^{3} (u_{R})$ of length $ℓ = 3$ in $R - F_{R}$ as follows. $\begin{array}{llll} P_{i}^{3} (u_{R}) = {\begin{cases} (i + j - 2, & j, & j - 1), & i = 1, \\ (i + j - 2, & j + 1, & j + 2), & i = 2 \land x_{j - 1} = x_{j + 1}, \\ (i + j - 2, & j + 2, & j + 1), & i = 2 \land x_{j - 1} \neq x_{j + 1} . \end{cases} \end{array}$

For $j \geq n - 1$ , there exist two disjoint $u_{R} v_{R}$ -paths as $P_{i}^{3} (u_{R})$ of length $ℓ = 3$ in $R - F_{R}$ as follows. $\begin{array}{llll} P_{i}^{3} (u_{R}) = {\begin{cases} (2, & j, & 2), & i = 1, \\ (j - 1, & j, & j - 1), & i = 2 . \end{cases} \end{array}$

Since $| F_{R} | \leq 1$ , there exists a fault-free $u_{R} v_{R}$ -path $P^{3} (u_{R})$ of length $ℓ = 3$ in $R - F_{R}$ . Then $C = u_{L} u_{R} + P^{3} (u_{R}) + v_{R} v_{L} + u_{L} v_{L}$ is a fault-free $6$ -cycle containing the edge $u_{L} v_{L}$ .

Case 2.2. $| {u_{R}, v_{R}} \cap F | = 1$ . Without loss of generality, assume that $u_{R} \in F$ . Let $F^{^{'}} = F - {u_{R}}$ , then $| F^{^{'}} | = n - 3$ .

For $j = 3$ , there exist $n - 2$ $6$ -cycles as $C_{i}^{6} (u_{L}) (1 \leq i \leq n - 2)$ containing the common edge $u_{L} v_{L}$ in $M Q_{n}^{1} - F^{^{'}}$ as follows. $\begin{array}{llll} C_{i}^{6} (u_{L}) = {\begin{cases} (i + 1, & 1, & 3, & 1, & 2), & i = 1, \\ i < j - 1. \\ (i + 2, & 3, & 1, & 4, & 1), & i = 2, \\ n - 3 \land x_{2} = 0 \land i < j - 1. \\ (i + 2, & n, & 3, & n, & i + 2), & 3 \leq i \leq n - 3 \land x_{2} = 0, \\ n - 3 \land x_{2} \neq 0 \land i < j - 1. \\ (i + 2, & 3, & 1, & i + 2, & 1), & 3 \leq i \leq n - 3 \land x_{2} \neq 0, \\ (i + 2, & 3, & 1, & n, & 1), & i = n - 2. \end{cases} \end{array}$

For $4 \leq j \leq n - 2$ , there exist $n - 2$ $6$ -cycles as $C_{i}^{6} (u_{L}) (1 \leq i \leq n - 2)$ containing the common edge $u_{L} v_{L}$ in $M Q_{n}^{1} - F^{^{'}}$ as follows: $\begin{array}{llll} C_{i}^{6} (u_{L}) = {\begin{cases} (i + 1, j, j + 1, 2, j + 1), i = 1, \\ (i + 1, n, j, n, i + 1), 2 \leq i \leq j - 3 \land x_{i} = 0, \\ (i + 1, j - 1, j, j - 1, i + 1), 2 \leq i \leq j - 3 \land x_{i} \neq 0, \\ (i + 1, j + 1, j + 2, j, j - 1), i = j - 2 \land x_{j - 2} = x_{j} \land x_{j - 2} = x_{j + 1}, \\ (i + 1, j + 2, j + 1, j, j - 1), i = j - 2 \land x_{j - 2} = x_{j} \land x_{j - 2} \neq x_{j + 1}, \\ (i + 1, j, j + 2, j + 1, j - 1), \\ i = j - 2 \land x_{j - 2} \neq x_{j} \land ((x_{j - 1} = x_{j + 1} \land x_{j - 2} = 0) \lor (x_{j - 1} \neq x_{j + 1} \land x_{j - 2} = 1)), \\ (i + 1, j, j + 1, j + 2, j - 1), \\ i = j - 2 \land x_{j - 2} \neq x_{j} \land ((x_{j - 1} \neq x_{j + 1} \lor x_{j - 2} \neq 0) \land (x_{j - 1} = x_{j + 1} \lor x_{j - 2} \neq 1)), \\ (i + 2, j, 1, j + 1, 1), i = j - 1, \\ (i + 2, 2, j, 2, i + 2), j \leq i \leq n - 2 \land x_{j - 1} = 0, \\ (i + 2, j, 1, i + 2, 1), j \leq i \leq n - 2 \land x_{j - 1} \neq 0. \end{cases} \end{array}$

For $j = n - 1$ , there exist $n - 2$ $6$ -cycles as $C_{i}^{6} (u_{L}) (1 \leq i \leq n - 2)$ containing the common edge $u_{L} v_{L}$ in $M Q_{n}^{1} - F^{^{'}}$ as follows. $\begin{array}{llll} C_{i}^{6} (u_{L}) = {\begin{cases} (i + 1, & n, & j, & n, & i + 1), & i \leq n - 4 \land x_{i} = 0, \\ (i + 1, & j - 1, & j, & j - 1, & i + 1), & i \leq n - 4 \land x_{i} \neq 0, \\ (i + 1, & n, & 1, & n - 2, & 1), & i = n - 3 \land x_{n - 2} = 0, \\ (i + 1, & 1, & n - 1, & 1, & n - 2), & i = n - 3 \land x_{n - 2} \neq 0, \\ (i + 2, & n - 1, & 1, & n, & 1), & i = n - 2 . \end{cases} \end{array}$

For $j = n$ , there exist $n - 2$ $6$ -cycles as $C_{i}^{6} (u_{L}) = (i + 1, i, n, i, i + 1)$ $(1 \leq i \leq n - 2)$ containing the common edge $u_{L} v_{L}$ in $M Q_{n}^{1} - F^{^{'}}$ .

Note that $n - 2$ $6$ -cycles are disjoint in $L$ and contain no $u_{R}$ in $M Q_{n}^{1} - F^{^{'}}$ . Since $| F^{^{'}} | = n - 3$ , we have that there exists a fault-free 6-cycles in $M Q_{n}^{1} - F^{^{'}}$ , and so in $M Q_{n}^{1} - F$ .

Take edge $u_{L} v_{L} = (001011, 001100)$ in $M Q_{6}^{1}$ for an example. We have $u_{R} = 110100$ , $v_{R} = 110011$ . Assume $110100 \in F$ , then $110011 \notin F$ . There exist four disjoint $6$ -cycles in $L$ except a common edge $u_{L} v_{L} = (001011, 001100)$ as follows(see Figure 2). $\begin{array}{llll} {\begin{cases} (001011, & 011011, & 011100, & 011111, & 001111, & 001100), \\ (001011, & 000011, & 000010, & 000000, & 000100, & 001100), \\ (001011, & 001001, & 001110, & 110001, & 110011, & 001100), \\ (001011, & 001010, & 001101, & 110010, & 110011, & 001100) . \end{cases} \end{array}$

Lemma 2.13. If $F \subset R$ with $| F | = n - 2$ ( $n \geq 6$ ), then for any edge $u_{R} v_{R} \in R$ , there exists a fault-free $6$ -cycle containing the edge $u_{R} v_{R}$ in $M Q_{n}^{1} - F$ .

Proof. Let $u_{L}, v_{L}$ be the adjacent vertices of $u_{R}, v_{R}$ respectively in $L$ and $u_{R} = x_{1} x_{2} \dots x_{i} \dots x_{n}$ . Since $F \subset R$ , $F_{L} = 0$ . There exists a fault-free $u_{L} v_{L}$ -path $P$ of length $ℓ = 3$ in $L$ as follows. $\begin{array}{llll} P = {\begin{cases} (2, & 4, & 3), & v_{R} = u_{R}^{2} \land x_{3} = 0, \\ (2, & 3, & 4), & v_{R} = u_{R}^{2} \land x_{3} \neq 0, \\ (j - 1, & j, & j - 1), & v_{R} = u_{R}^{j} (3 \leq j \leq n - 1), \\ (2, & n, & 2), & v_{R} = u_{R}^{n} . \end{cases} \end{array}$

Then $C = v_{R} v_{L} + P + u_{L} u_{R} + u_{R} v_{R}$ is a fault-free $6$ -cycle containing the edge $u_{R} v_{R}$ in $M Q_{n}^{1} - F$ .

Lemma 2.14. For any edge $u_{L} u_{R} \in E_{C}$ in $M Q_{n}^{i} - F$ ( $i = 0, 1$ )( $n \geq 6$ ) with $| F | \leq n - 2$ , there exists a fault-free cycle of length $ℓ = 7 - i, 7, 8$ containing the edge $u_{L} u_{R}$ in $M Q_{n}^{i} - F$ ( $i = 0, 1$ ).

Proof. Let $u_{L} = x_{1} x_{2} x_{3} \dots x_{i} \dots x_{n}$ . We prove the lemma according to edge $u_{L} u_{R}$ in $M Q_{n}^{0}$ or $M Q_{n}^{1}$ as follows.

Case 1. $u_{L} u_{R} \in E (M Q_{n}^{0})$ .

Case 1.1. $ℓ = 7$ .

For $1 \leq i \leq n - 1$ , we can find $n - 1$ disjoint $7$ -cycles as $C_{i}^{7} (u_{L})$ except the common edge $u_{L} u_{R}$ as follows. $\begin{array}{llll} C_{1}^{7} (u_{L}) = {\begin{cases} (2, & 3, & n - 1, & 1, & n - 1, & 2), & x_{3} = 0 \land x_{2} = 0, \\ (2, & 3, & 2, & 1, & 4, & 3), & x_{3} = 0 \land x_{2} \neq 0, \\ (2, & 1, & 2, & 5, & 4, & 3), & x_{3} \neq 0 \land x_{2} = 0 \land x_{4} = 0, \\ (2, & 1, & 5, & 2, & 4, & 3), & x_{3} \neq 0 \land x_{2} = 0 \land x_{4} \neq 0, \\ (2, & n, & 1, & n, & 2, & 3), & x_{3} \neq 0 \land x_{2} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{2}^{7} (u_{L}) = {\begin{cases} (3, & 2, & 3, & 1, & 2, & 3), & x_{3} = 0 \land x_{2} = 0, \\ (3, & 2, & 3, & 1, & 3, & 2), & x_{3} = 0 \land x_{2} \neq 0, \\ (3, & 4, & 2, & 1, & 5, & 2), & x_{3} \neq 0 \land x_{2} = 0 \land x_{4} = 0, \\ (3, & 5, & 2, & 1, & 4, & 2), & x_{3} \neq 0 \land x_{2} = 0 \land x_{4} \neq 0, \\ (3, & 4, & 2, & 1, & 4, & 2), & x_{3} \neq 0 \land x_{2} \neq 0 \land x_{4} = 0, \\ (3, & 5, & 2, & 1, & 5, & 2), & x_{3} \neq 0 \land x_{2} \neq 0 \land x_{4} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{i}^{7} (u_{L}) = {\begin{cases} (i + 1, & 2, & 3, & 1, & 2, & i + 1), & 3 \leq i \leq n - 1 \land x_{2} = 0, \\ (i + 1, & 3, & 2, & 1, & 2, & i + 1), & 3 \leq i \leq n - 1 \land x_{2} \neq 0. \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $7$ -cycle containing the edge $u_{L} u_{R}$ .

Case 1.2. $ℓ = 8$ .

For $1 \leq i \leq n - 1$ , we can find $n - 1$ disjoint $8$ -cycles as $C_{i}^{8} (u_{L})$ except the common edge $u_{L} u_{R}$ as follows. $\begin{array}{llll} C_{1}^{8} (u_{L}) = {\begin{cases} (2, & 1, & n - 1, & 3, & n - 1, & 2), & x_{2} = 0, \\ (2, & 3, & 2, & 1, & 2, & 3), & x_{2} \neq 0, \end{cases} \end{array}$

$C_{i}^{8} (u_{L}) = (i + 1, 2, n, 2, 1, n), 2 \leq i \leq n - 2,$

$\begin{array}{llll} C_{n - 1}^{8} (u_{L}) = {\begin{cases} (n, & 2, & 1, & n - 1, & 3, & n - 1), & x_{2} = 0, \\ (n, & 2, & 1, & 3, & 4, & 2), & x_{2} \neq 0 \land x_{3} = 0, \\ (n, & 2, & 1, & 4, & 3, & 2), & x_{2} \neq 0 \land x_{3} \neq 0. \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $8$ -cycle containing the edge $u_{L} u_{R}$ .

Take edge $(010010, 110010)$ in $M Q_{6}^{0}$ for an example, there exist $5$ disjoint $8$ -cycles except the common edge $(010010, 110010)$ as follows(see Figure 3). $\begin{array}{llll} {\begin{cases} (010010, 000010, 001010, 011010, 111010, 100101, 101101, 110010), \\ (010010, 011101, 001101, 001100, 011100, 111100, 111101, 110010), \\ (010010, 010110, 000110, 000111, 010111, 110111, 110110, 110010), \\ (010010, 010000, 000000, 000001, 010001, 110001, 110000, 110010), \\ (010010, 010011, 000011, 100011, 101011, 101100, 110011, 110010) . \end{cases} \end{array}$

Figure 3 $5$ disjoint $8$ -cycles except the common edge $(010010, 110010)$ in $M Q_{6}^{0}$

Case 2. $u_{L} u_{R} \in E (M Q_{n}^{1})$ .

Case 2.1. $ℓ = 6$ .

For $1 \leq i \leq n - 1$ , we can find $n - 1$ disjoint $6$ -cycles as $C_{i}^{6} (u_{L})$ except the common edge $u_{L} u_{R}$ as follows. $\begin{array}{llll} C_{i}^{6} (u_{L}) = {\begin{cases} (i + 1, 1, i + 3, i + 2, i + 1), 1 \leq i \leq n - 4 \land x_{i} = x_{i + 2} \land x_{i + 1} = 0, \\ (i + 1, i + 2, i + 3, 1, i + 1), 1 \leq i \leq n - 4 \land x_{i} = x_{i + 2} \land x_{i + 1} \neq 0, \\ (i + 1, i + 3, 1, i + 2, i + 1), 1 \leq i \leq n - 4 \land x_{i} \neq x_{i + 2} \land x_{i + 1} = 0, \\ (i + 1, i + 2, 1, i + 3, i + 1), 1 \leq i \leq n - 4 \land x_{i} \neq x_{i + 2} \land x_{i + 1} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 3}^{6} (u_{L}) = {\begin{cases} (n - 2, & n - 1, & n - 2, & 1, & n - 1), & x_{n - 2} = 0, \\ (n - 2, & n - 1, & 1, & n - 2, & n), & x_{n - 2} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 2}^{6} (u_{L}) = {\begin{cases} (n - 1, & n - 2, & 1, & n - 2, & n), & x_{n - 2} = 0, \\ (n - 1, & 1, & n - 2, & n - 1, & n - 2), & x_{n - 2} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 1}^{6} (u_{L}) = {\begin{cases} (n, & n - 2, & 1, & n - 1, & n - 2), & x_{n - 2} = 0, \\ (n, & n - 2, & 1, & n - 2, & n - 1), & x_{n - 2} \neq 0. \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $6$ -cycle containing the edge $u_{L} u_{R}$ .

Case 2.2. $ℓ = 7$ .

For $1 \leq i \leq n - 1$ , we can find $n - 1$ disjoint $7$ -cycles as $C_{i}^{7} (u_{L})$ except the common edge $u_{L} u_{R}$ as follows.

$\begin{array}{llll} C_{i}^{7} (u_{L}) = {\begin{cases} (i + 1, i + 3, i + 2, 1, i + 3, i + 1), & 1 \leq i \leq n - 4 \land x_{i + 1} = 0, \\ (i + 1, i + 3, 1, i + 2, i + 3, i + 1), & 1 \leq i \leq n - 4 \land x_{i + 1} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 3}^{7} (u_{L}) = {\begin{cases} (n - 2, & 1, & n, & n - 2, & n, & n - 1), & x_{n - 2} = 0, \\ (n - 2, & 1, & n, & n - 1, & n - 2, & n), & x_{n - 2} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 2}^{7} (u_{L}) = {\begin{cases} (n - 1, n - 2, n - 3, 1, n - 3, n), x_{n - 2} = 0 \land x_{n - 3} = 0, \\ (n - 1, n, n - 3, 1, n - 3, n - 2), x_{n - 2} = 0 \land x_{n - 3} \neq 0 \land x_{n - 4} = 0, \\ (n - 1, n - 3, n - 2, 1, n - 3, n), x_{n - 2} = 0 \land x_{n - 3} \neq 0 \land x_{n - 4} \neq 0, \\ (n - 1, 2, n - 2, 2, 1, n - 2), x_{n - 2} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 1}^{7} (u_{L}) = {\begin{cases} (n, n - 3, 1, n - 3, n, n - 2), x_{n - 2} = 0 \land x_{n - 3} = 0, \\ (n, n - 2, n - 3, 1, n - 3, n), x_{n - 2} = 0 \land x_{n - 3} \neq 0 \land x_{n - 4} = 0, \\ (n, n - 2, n - 1, 1, n, n - 2), x_{n - 2} = 0 \land x_{n - 3} \neq 0 \land x_{n - 4} \neq 0, \\ (n, 2, n - 1, 2, 1, n - 1), x_{n - 2} \neq 0 . \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $7$ -cycle containing the edge $u_{L} u_{R}$ .

Case 2.3. $ℓ = 8$ .

For $1 \leq i \leq n - 1$ , we can find $n - 1$ disjoint $8$ -cycles as $C_{i}^{8} (u_{L})$ except the common edge $u_{L} u_{R}$ as follows. $\begin{array}{llll} C_{i}^{8} (u_{L}) = {\begin{cases} (i + 1, n, 1, n, i + 3, i + 2), 1 \leq i \leq n - 4 \land x_{i} = x_{i + 2} \land x_{i + 1} = 0, \\ (i + 1, i + 2, i + 3, n, 1, n), 1 \leq i \leq n - 4 \land x_{i} = x_{i + 2} \land x_{i + 1} \neq 0, \\ (i + 1, i + 3, n, 1, n, i + 2), 1 \leq i \leq n - 4 \land x_{i} \neq x_{i + 2} \land x_{i + 1} = 0, \\ (i + 1, i + 2, n, 1, n, i + 3), 1 \leq i \leq n - 4 \land x_{i} \neq x_{i + 2} \land x_{i + 1} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 3}^{8} (u_{L}) = {\begin{cases} (n - 2, & 1, & n - 1, & 1, & n, & 1), & x_{n - 2} = 0, \\ (n - 2, & 1, & n, & 1, & n - 1, & 1), & x_{n - 2} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 2}^{8} (u_{L}) = {\begin{cases} (n - 1, & 2, & n, & 3, & 1, & 2), & x_{2} = 0, \\ (n - 1, & 2, & n, & 1, & 3, & 2), & x_{2} \neq 0, \end{cases} \end{array}$ $\begin{array}{llll} C_{n - 1}^{8} (u_{L}) = {\begin{cases} (n, n - 2, 1, 2, n - 2, 2), x_{2} = 0 \land x_{n - 2} = 0, \\ (n, n - 1, n - 2, n - 3, 1, n - 3), x_{2} = 0 \land x_{n - 2} \neq 0 \land x_{n - 3} = 0, \\ (n, n - 1, n - 3, 1, n - 3, n - 2), x_{2} = 0 \land x_{n - 2} \neq 0 \land x_{n - 3} \neq 0, \\ (n, 2, 3, 2, 1, 3), x_{2} \neq 0 \land x_{3} = 0, \\ (n, 2, 4, 3, 1, 2), x_{2} \neq 0 \land x_{3} \neq 0 . \end{cases} \end{array}$

Since $| F | \leq n - 2$ , there exists a fault-free $8$ -cycle containing the edge $u_{L} u_{R}$ .

Take edge $(010010, 101101)$ in $M Q_{6}^{1}$ for an example, there exist $5$ disjoint $8$ -cycles except the common edge $(010010, 101101)$ as follows (see Figure 4): $\begin{array}{llll} {\begin{cases} (010010, 000010, 001010, 001101, 001100, 110011, 110010, 101101), \\ (010010, 011101, 011110, 011111, 100000, 100001, 100101, 101101), \\ (010010, 010110, 101001, 101011, 010100, 010101, 101010, 101101), \\ (010010, 010000, 000000, 000001, 111110, 110001, 101110, 101101), \\ (010010, 010011, 000011, 001011, 011011, 100100, 101100, 101101) . \end{cases} \end{array}$

Figure 4 5 disjoint 8-cycles except the common edge (010010, 101101) in $M Q_{6}^{1}$

3. Fault-tolerant edge-pancyclicity of $M Q_{n}$

In this section, we investigate the fault-tolerant edge-Pancyclicity of $M Q_{n}$ and show that $M Q_{n}$ is $(n - 2)$ -fault-tolerant edge-Pancyclic.

Let $F$ be a set of faulty elements in $M Q_{n}$ , $F_{L} = F \cap L$ , $F_{R} = F \cap R$ , $F_{C} = F \cap E_{C}$ , $F^{v} = F \cap V (M Q_{n})$ , $F^{e} = F \cap E (M Q_{n})$ $F_{L}^{v} = F_{L} \cap V (L)$ and $F_{R}^{v} = F_{R} \cap V (R)$ , $f_{v} = | F^{v} |$ , $f_{e} = | F^{e} |$ .

Theorem 3.1. If $f_{v} + f_{e} \leq n - 2$ and $n \geq 5$ then, for any fault-free edge $e$ in $M Q_{n}^{i} (i = 0, 1)$ and any integer $ℓ$ with $7 - i \leq ℓ \leq 2^{n} - f_{v}$ , there is a fault-free cycle of length $ℓ$ containing the edge $e$ .

In this section, we will give the proof of Theorem 3.1. The theorem follows from Lemma 2.10 if $| F | ⩽ n - 3$ . We only need to consider $| F | = n - 2$ . Start with the following lemma.

Lemma 3.2. If Theorem 3.1 holds for any subset $F \subset V (M Q_{n})$ with $| F | = n - 2$ , then Theorem 3.1 also holds for any subset $F^{^{'}} \subset V (M Q_{n}) \cup E (M Q_{n})$ with $| F^{^{'}} | = n - 2$ .

Proof. The lemma holds for $f_{e} = 0$ by hypothesis of Lemma 3.2. Assume that the lemma holds for any $t$ with $0 < t \leq n - 3$ and $f_{e} = t$ . We prove the lemma holds for $f_{e} = t + 1$ . Let $x y$ be an edge in $F$ .

Case 1. $x \in F$ or $y \in F$ .

Without loss of generality, assume $x \in F$ . Let $F^{^{'}} = F - x y$ , then $| F^{^{'}} | = n - 3$ . By Lemma 2.10, this result has been proved.

Case 2. $x, y \notin F$ .

Let $F^{^{'}} = F + {x} - {x y}$ , then $| F^{^{'}} | = n - 2$ , and $F^{^{'}}$ contains at most $t$ edges and $f_{v} + 1$ vertices. By induction hypothesis, for every integer $ℓ$ with $7 - i \leq ℓ \leq 2^{n} - f_{v} - 1$ , there is a fault-free $ℓ$ -cycle containing the edge $e$ in $M Q_{n}^{i} - F^{^{'}}$ ( $i = 0, 1$ ). By Proposition 2.1, for any $e = u v \in E (M Q_{n} - F)$ , $(u, v)$ is not a weak vertex-pair in $M Q_{n} - F$ . For $ℓ = 2^{n} - f_{v}$ , by Lemma 2.11, there is a fault-free $u v$ -hamiltonian path in $M Q_{n} - F$ , i.e., there is a fault-free $ℓ$ -cycle containing the edge $e$ in $M Q_{n} - F$ .

The proof of lemma is completed.

Proof of Theorem 3.1. By Lemma 3.2, we only need to prove the theorem with $F \subset V (M Q_{n})$ . The proof proceeds by induction on $n ⩾ 5$ . The result holds for $n = 5$ by developing computer program using depth first searching technique combining with backtracking and branch and bound algorithm.

Assume that the theorem holds for any $k$ with $6 \leq k < n$ . Then we must show the theorem holds for $n$ .

Let $e = u v$ be a fault-free edge in $M Q_{n}$ . By Proposition 2.3, $(u, v)$ is not a weak vertex-pair in $M Q_{n} - F$ . Let $2^{n - 1} \leq ℓ \leq 2^{n} - f_{v}$ and $ℓ = ℓ^{'} + 1$ , where $2^{n - 1} - 1 \leq ℓ^{'} \leq 2^{n} - f_{v} - 1$ then, by Lemma 2.11, there exists a fault-free $u v$ -path $P$ of length $ℓ^{'}$ in $M Q_{n}$ . Then $P + u v$ is a fault-free cycle of length $ℓ$ containing the edge $e$ in $M Q_{n}$ . Thus, we only need to consider $ℓ$ with $7 - i \leq ℓ \leq 2^{n - 1} - 1$ in $M Q_{n}^{i} (i = 0, 1)$ ( $n \geq 6$ ).

Case 1. $| F_{R} | \leq | F_{L} |$ .

Case 1.1. $e \in E (L - F_{L})$ . Let $e = u_{L} v_{L}$ .

By Lemma 2.12, there exists a fault-free $6$ -cycle containing the edge $e$ in $M Q_{n}^{1} - F$ . Thus, we only need to consider the length of $7 \leq ℓ \leq 2^{n - 1} - 1$ .

Case 1.1.1. $| F_{L} | \leq n - 3$ . Then $| F_{R} | \leq n - 4$ .

Case 1.1.1.1. $7 \leq ℓ \leq 2^{n - 1} - | F_{L}^{v} |$ .

By induction hypothesis, there is a fault-free cycle of length $ℓ$ containing the edge $e$ in $L$ , so in $M Q_{n}$ .

Case 1.1.1.2. $2^{n - 1} - | F_{L}^{v} | + 1 \leq ℓ \leq 2^{n - 1} - 1$ .

Write $ℓ = ℓ_{1} + 1 + ℓ_{2}$ , where $2^{n - 2} - | F_{L}^{v} | + 1 \leq ℓ_{1} \leq 2^{n - 2} - 1$ and $ℓ_{2} = 2^{n - 2} - 1$ . Since $2^{n - 2} - | F_{L}^{v} | + 1 \geq 2^{n - 2} - | F_{L} | + 1 \geq 2^{n - 2} - n + 4 > 7$ for $n \geq 6$ and $| F_{L} | \leq n - 3$ , by induction hypothesis, there is a fault-free cycle $C$ of length $ℓ_{1}$ containing the edge $u_{L} v_{L}$ in $L$ . Note that a cycle of length $ℓ_{1}$ contains a matching $M$ with $| M | = ⌊ \frac{ℓ_{1}}{2} ⌋$ . Consider the following inequality. $\begin{aligned} ⌊ \frac{ℓ_{1}}{2} ⌋ - | F_{C} | - | F_{R} | - | {e} | & \geq ⌊ \frac{2^{n - 2} - | F_{L}^{v} | + 1}{2} ⌋ - | F_{C} | - | F_{R} | - 1 \\ \geq 2^{n - 3} - | F | - 1 \geq 2^{n - 3} - n + 1. \end{aligned}$

Let $f (x) = 2^{x - 3} - x + 1$ . Since $f^{'} (x) = 2^{x - 3} \ln 2 - 1 \geq 0$ for $x \geq 6$ , $f (x)$ is an increasing function, which implies that $⌊ \frac{ℓ_{1}}{2} ⌋ - | F_{C} | - | F_{R} | \geq f (6) = 2^{6 - 3} - 6 + 1 = 3$ . It follows that, there is such an edge, say $x_{L} y_{L}$ , in $M$ that $x_{L} y_{L} \neq u_{L} v_{L}$ and $| {x_{R}, y_{R}, x_{L} x_{R}, y_{L} y_{R}} \cap F | = 0$ . By Lemma 2.1, there is a fault-free $x_{R} y_{R}$ -path $P$ of length $ℓ_{2}$ in $R$ . Then $C - x_{L} y_{L} + y_{L} y_{R} + P + x_{R} x_{L}$ is a fault-free cycle of length $ℓ (= ℓ_{1} + 1 + ℓ_{2})$ containing $e$ (see Figure 5 (a)).

Case 1.1.2. $| F_{L} | = n - 2$ . In this case, $| F_{R} | = 0$ .

Let $u_{R}$ and $v_{R}$ be neighbors of $u_{L}$ and $v_{L}$ in $R$ , respectively.

Let $ℓ = ℓ^{'} + 3$ , where $4 \leq ℓ^{'} \leq 2^{n - 1} - 4$ . By Lemma 2.4, $d_{u_{R} v_{R}} \leq 2$ . Since $| F_{R} | = | F_{C} | = 0$ , by Lemma 2.6, there is a fault-free $u_{R} v_{R}$ -path $P$ of length $ℓ^{'}$ in $R$ , and so $P + v_{R} v_{L} + v_{L} u_{L} + u_{L} u_{R}$ is a fault-free cycle of length $ℓ$ containing the edge $u_{L} v_{L}$ (see Figure 5 (b)).

Case 1.2. $e \in E (R - F_{R})$ . Let $e = u_{R} v_{R}$ .

Case 1.2.1. $| F_{L} | \leq n - 3$ . Then $| F_{R} | \leq n - 4$ .

Case 1.2.1.1. $7 - i \leq ℓ \leq 2^{n - 1} - | F_{R}^{v} |$ in $M Q_{n}^{i} (i = 0, 1)$ .

By induction hypothesis, there is a fault-free cycle of length $ℓ$ containing the edge $e$ in $R$ , so in $M Q_{n}^{i} (i = 0, 1)$ .

Case 1.2.1.2. $2^{n - 1} - | F_{R}^{v} | + 1 \leq ℓ \leq 2^{n - 1} - 1$ .

The proof is similar to Case 1.1.1.2.

Case 1.2.2. $| F_{L} | = n - 2$ . In this case, $| F_{R} | = 0$ .

Since $| F_{R} | = 0$ , by Lemma 2.5, there exists a fault-free cycle of length $ℓ$ with $7 - i \leq ℓ \leq 2^{n - 1} - 1$ containing the edge $e$ in $R$ , and so in $M Q_{n}^{i} - F (i = 0, 1)$ .

Case 1.3. $e \in (E_{C} - F_{C})$ . Let $e = u_{L} u_{R}$ .

By Lemma 2.14, there exists a fault-free cycle of length $ℓ = 7 - i, 7, 8$ containing the edge $u_{L} u_{R}$ in $M Q_{n}^{i} - F$ ( $i = 0, 1$ ). Thus, we only need to consider the length $9 \leq ℓ \leq 2^{n - 1} - 1$ .

Case 1.3.1. $| F_{L} | \leq n - 3$ . Then $| F_{R} | \leq n - 4$ .

By Corollary 2.1., there exists a fault-free $4$ -cycle $C$ (or $5$ -cycle) containing the edge $u_{L} u_{R}$ .

Case 1.3.1.1. $C = C^{4} = (u_{L}, s_{L}, s_{R}, u_{R})$ .

For $9 \leq ℓ \leq 2^{n - 1} - | F_{R}^{v} | - 1$ . Let $ℓ = ℓ^{'} + 2$ , where $7 \leq ℓ^{'} \leq 2^{n - 1} - | F_{R}^{v} | - 3$ . By induction hypothesis, there is a fault-free cycle $C^{'}$ of length $ℓ^{'}$ containing the edge $u_{R} s_{R}$ in $R$ . Then $C = C^{'} - u_{R} s_{R} + s_{R} s_{L} + s_{L} u_{L} + u_{L} u_{R}$ is a fault-free cycle of length $ℓ$ containing the edge $e = u_{L} u_{R}$ .

For $2^{n - 1} - | F_{R}^{v} | \leq ℓ \leq 2^{n - 1} - 1$ . Let $ℓ = ℓ_{1} + ℓ_{2}$ , where $ℓ_{1} = 2^{n - 2}$ and $2^{n - 2} - | F_{R}^{v} | \leq ℓ_{2} \leq 2^{n - 2} - 1$ . Since $2^{n - 2} > 7$ and $2^{n - 2} - | F_{R}^{v} | > 7$ for $n \geq 6$ , by induction hypothesis, there exists a fault-free cycle $C_{1}$ of length $ℓ_{1}$ containing the edge $u_{L} s_{L}$ in $L$ and a fault-free cycle $C_{2}$ of length $ℓ_{2}$ containing the edge $u_{R} s_{R}$ in $R$ . Then $C = C_{1} - u_{L} s_{L} + s_{L} s_{R} + C_{2} - s_{R} u_{R} + u_{R} u_{L}$ is a fault-free cycle of length $ℓ$ containing the edge $e = u_{L} u_{R}$ in $M Q_{n}$ (see Figure 6(a)).

Case 1.3.1.2. $C = C^{5} = (u_{L}, w_{L}, w_{R}, x, u_{R})$ .

Since $| F_{R} | \leq n - 4$ . Let $F_{R}^{1} = F_{R} - {w_{R}}$ , then $| F_{R}^{1} | = | F_{R} | - 1 \leq n - 3$ .

For $9 \leq ℓ \leq 2^{n - 1} - | F_{R}^{v} | - 1$ . Let $ℓ = ℓ^{'} + 3$ , where $6 \leq ℓ^{'} \leq 2^{n - 1} - | F_{R}^{v} | - 4$ . By induction hypothesis, there is a fault-free cycle $C^{'}$ of length $ℓ^{'}$ containing the edge $u_{R} x$ in $R - F_{R}^{1}$ . Then $C = C^{'} - u_{R} x + x w_{R} + w_{R} w_{L} + w_{L} u_{L} + u_{L} u_{R}$ is a fault-free cycle of length $ℓ$ containing the edge $e = u_{L} u_{R}$ .

For $2^{n - 1} - | F_{R}^{v} | \leq ℓ \leq 2^{n - 1} - 1$ . Let $ℓ = ℓ_{1} + ℓ_{2} + 2$ , where $ℓ_{1} = 2^{n - 2} - 1$ and $2^{n - 2} - | F_{R}^{v} | - 1 \leq ℓ_{2} \leq 2^{n - 2} - 2$ . Since $2^{n - 2} - | F_{R}^{v} | - 1 > 7$ for $n \geq 6$ , by induction hypothesis, there exists a fault-free cycle $C_{1}$ of length $ℓ_{2}$ containing the edge $x u_{R}$ in $R - F_{R}^{1}$ and, by Lemma 2.11, there exists a fault-free $u_{L} w_{L}$ -path $P$ of length $ℓ_{1}$ in $L$ . Then $C = C_{1} - u_{R} x + x w_{R} + w_{R} w_{L} + P + u_{L} u_{R}$ is a fault-free cycle of length $ℓ$ containing the edge $e = u_{L} u_{R}$ in $M Q_{n}$ (see 6(b)).

Figure 6 The illustration of Case 1.3.1.1. and Case 1.3.1.2.

Case 1.3.1.3. $C = C^{5} = (u_{L}, x, w_{L}, w_{R}, u_{R})$ .

For $9 \leq ℓ \leq 2^{n - 1} - | F_{R}^{v} | - 1$ . Let $ℓ = ℓ^{'} + 3$ , where $6 \leq ℓ^{'} \leq 2^{n - 1} - | F_{R}^{v} | - 4$ . By induction hypothesis, there is a fault-free cycle $C^{'}$ of length $ℓ^{'}$ containing the edge $u_{R} w_{R}$ in $R$ . Then $C = C^{'} - u_{R} w_{R} + w_{R} w_{L} + w_{L} x + x u_{L} + u_{L} u_{R}$ is a fault-free cycle of length $ℓ$ containing the edge $e = u_{L} u_{R}$ .

For $2^{n - 1} - | F_{R}^{v} | \leq ℓ \leq 2^{n - 1} - 1$ . Let $ℓ = ℓ_{1} + ℓ_{2} + 1$ , where $ℓ_{1} = 2^{n - 2}$ and $2^{n - 2} - | F_{R}^{v} | - 1 \leq ℓ_{2} \leq 2^{n - 2} - 2$ . Since $2^{n - 2} - | F_{R}^{v} | - 1 > 7$ for $n \geq 6$ , by induction hypothesis, there exists a fault-free cycle $C_{1}$ of length $ℓ_{2}$ containing the edge $u_{R} w_{R}$ in $R$ and, by Lemma 2.11, there exists a fault-free $u_{L} w_{L}$ -path $P$ of length $ℓ_{1}$ in $L$ . Then $C = C_{1} - u_{R} w_{R} + w_{R} w_{L} + P + u_{L} u_{R}$ is a fault-free cycle of length $ℓ$ containing the edge $u_{L} u_{R}$ in $M Q_{n}$ (see Figure 7(a)).

Case 1.3.2. $| F_{L} | = n - 2$ . In this case, $| F_{R} | = 0$ .

Since $| F_{L} | = n - 2$ , there exists a fault-free neighbor $v_{L}$ of $u_{L}$ in $L$ . Let $v_{R}$ be neighbors of $v_{L}$ in $R$ .

Let $ℓ = ℓ^{'} + 3$ , where $6 \leq ℓ^{'} \leq 2^{n - 1} - 4$ . By Lemma 2.4, $d_{u_{R} v_{R}} \leq 2$ . By Lemma 2.6, there is a fault-free $u_{R} v_{R}$ -path $P$ of length $ℓ^{'}$ in $R$ . So $P + u_{R} u_{L} + u_{L} v_{L} + v_{L} v_{R}$ is a fault-free cycle of length $ℓ$ containing the edge $u_{L} u_{R}$ .

Case 2. $| F_{L} | \leq | F_{R} |$ .

Case 2.1. $e \in E (R - F_{R})$ . Let $e = u_{R} v_{R}$ .

Case 2.1.1. $| F_{R} | \leq n - 3$ . Then $| F_{L} | \leq n - 4$ .

For $7 - i \leq ℓ \leq 2^{n - 1} - | F_{R}^{v} |$ in $M Q_{n}^{i} (i = 0, 1)$ . By induction hypothesis, there is a fault-free cycle of length $ℓ$ containing the edge $e$ in $R$ , so in $M Q_{n}^{i} (i = 0, 1)$ .

For $2^{n - 1} - | F_{R}^{v} | + 1 \leq ℓ \leq 2^{n - 1} - 1$ . The proof is similar to Case 1.1.1.2.

Case 2.1.2. $| F_{R} | = n - 2$ . In this case, $| F_{L} | = 0$ .

By Lemma 2.13, there exists a fault-free $6$ -cycle containing the edge $e$ in $M Q_{n}^{1} - F$ . Thus, we only need to consider the length of $7 \leq ℓ \leq 2^{n - 1} - 1$ .

Let $u_{L}$ and $v_{L}$ be neighbors of $u_{R}$ and $v_{R}$ in $L$ , respectively.

Let $ℓ = ℓ^{'} + 3$ , where $4 \leq ℓ^{'} \leq 2^{n - 1} - 4$ . By Lemma 2.4, $d_{u_{L} v_{L}} \leq 2$ . Since $| F_{L} | = | F_{C} | = 0$ , by Lemma 2.6, there is a fault-free $u_{L} v_{L}$ -path $P$ of length $ℓ^{'}$ in $L$ , and so $P + v_{L} v_{R} + v_{R} u_{R} + u_{R} u_{L}$ is a fault-free cycle of length $ℓ$ containing the edge $u_{R} v_{R}$ .

Case 2.2. $e \in E (L - F_{L})$ . Let $e = u_{L} v_{L}$ .

Case 2.2.1. $| F_{R} | \leq n - 3$ . Then $| F_{L} | \leq n - 4$ .

For $7 - i \leq ℓ \leq 2^{n - 1} - | F_{L}^{v} |$ in $M Q_{n}^{i} - F$ $(i = 0, 1)$ . Since $| F_{L} | \leq n - 4$ , by Lemma 2.10, there exists a fault-free cycle of length $ℓ$ containing the edge $e$ in $M Q_{n}^{i} - F$ $(i = 0, 1)$ .

For $2^{n - 1} - | F_{L}^{v} | + 1 \leq ℓ \leq 2^{n - 1} - 1$ . The proof is similar to Case 1.1.1.2.

Case 2.2.2. $| F_{R} | = n - 2$ . In this case, $| F_{L} | = 0$ .

Since $| F_{L} | = 0$ , by Lemma 2.5, there exists a fault-free cycle of length $ℓ$ with $7 - i \leq ℓ \leq 2^{n - 1} - 1$ containing the edge $e$ in $L$ , and so in $M Q_{n}^{i} (i = 0, 1)$ .

Case 2.3. $e \in (E_{C} - F_{C})$ . Let $e = u_{L} u_{R}$ .

Case 2.3.1. $| F_{R} | \leq n - 3$ . Then $| F_{L} | \leq n - 4$ .

By Corollary 2.1., there exists a fault-free $4$ -cycle $C$ (or $5$ -cycle) containing the edge $u_{L} u_{R}$ .

Case 2.3.1.1. $C = C^{4} = (u_{L}, s_{L}, s_{R}, u_{R})$ .

The proof is similar to Case 1.3.1.1.

Case 2.3.1.2. $C = C^{5} = (u_{L}, w_{L}, w_{R}, x, u_{R})$ .

For $9 \leq ℓ \leq 2^{n - 1} - | F_{L}^{v} | - 1$ . Let $ℓ = ℓ^{'} + 3$ , where $6 \leq ℓ^{'} \leq 2^{n - 1} - | F_{L}^{v} | - 4$ . Since $| F_{L} | \leq n - 4$ , by Lemma 2.10, there is a fault-free cycle $C^{'}$ of length $ℓ^{'}$ containing the edge $u_{L} w_{L}$ in $L - F_{L}$ . Then $C = C^{'} - u_{L} w_{L} + w_{L} w_{R} + w_{R} x + x u_{R} + u_{R} u_{L}$ is a fault-free cycle of length $ℓ$ containing the edge $e = u_{L} u_{R}$ .

For $2^{n - 1} - | F_{L}^{v} | \leq ℓ \leq 2^{n - 1} - 1$ . Let $ℓ = ℓ_{1} + ℓ_{2} + 1$ , where $2^{n - 2} - | F_{L}^{v} | - 1 \leq ℓ_{1} \leq 2^{n - 2} - 2$ and $ℓ_{2} = 2^{n - 2}$ . Since $2^{n - 2} - | F_{L}^{v} | - 1 > 7$ for $n \geq 6$ , by induction hypothesis, there exists a fault-free cycle $C_{1}$ of length $ℓ_{1}$ containing the edge $u_{L} w_{L}$ in $L - F_{L}$ and, by Lemma 2.11, there exists a fault-free $u_{R} w_{R}$ -path $P$ of length $ℓ_{2}$ in $R$ . Then $C = C_{1} - u_{L} w_{L} + w_{L} w_{R} + P + u_{R} u_{L}$ is a fault-free cycle of length $ℓ$ containing the edge $e = u_{L} u_{R}$ in $M Q_{n}$ (see Figure 7(b)).

Figure 7 The illustration of Case 1.3.1.3. and Case 2.3.1.2.

Case 2.3.1.3. $C = C^{5} = (u_{L}, x, w_{L}, w_{R}, u_{R})$ .

The proof is similar to Case 1.3.1.3.

Case 2.3.2. $| F_{R} | = n - 2$ . In this case, $| F_{L} | = 0$ .

Since $| F_{R} | = n - 2$ , there exists a fault-free neighbor $v_{R}$ of $u_{R}$ in $R$ . Let $v_{L}$ be the neighbor of $v_{R}$ in $L$ . Let $ℓ = ℓ^{'} + 3$ , where $6 \leq ℓ^{'} \leq 2^{n - 1} - 4$ . By Lemma 2.4, $d_{u_{L} v_{L}} \leq 2$ . By Lemma 2.6, there is a fault-free $u_{L} v_{L}$ -path $P$ of length $ℓ^{'}$ in $L$ . So $P + u_{L} u_{R} + u_{R} v_{R} + v_{R} v_{L}$ is a fault-free cycle of length $ℓ$ containing the edge $u_{L} u_{R}$ .

The proof of the theorem is completed.

4. Conclusion and remarks

As one of the most fundamental networks for parallel and distributed computation, cycles are suitable for developing simple algorithms with low communication cost. Edge and/or vertex failures are inevitable when a large parallel computer system is put in use. Therefore, the fault-tolerant capacity of a network is a critical issue in parallel computing. The fault-tolerant edge-pancyclicity of an interconnection network is a measure of its capability of implementing ring-structured parallel algorithms in a communication-efficient fashion in the presence of faults.

In view of the fact that the hypercube network $Q_{n}$ contains only even cycles, $M Q_{n}$ is superior to $Q_{n}$ in fault-tolerant pancyclicity. This shows that, when the $M Q_{n}$ is used to model the topological structure of a large-scale parallel processing system, our result implies that the system has larger capability of implementing ring-structured parallel algorithms in a communication-efficient fashion in the hybrid presence of edge and vertex failures than one of the hypercube network.

We make some remarks on the optimality of our result in the following sense.

For $ℓ = 4$ , in $M Q_{5}^{0}$ , taking $e = (11011, 11100)$ , there are only two cycles: $(11011, 11010, 11101, 11100)$ , $(11011, 01011, 01100, 11100)$ of length 4 containing the edge $e$ (we calculate it by computer).

If $F = {01011, 11101}$ , then there exists no fault-free cycle of length 4 containing the edge $e$ in $M Q_{5}^{0} - F$ . In $M Q_{5}^{1}$ , taking $e = (11101, 11110)$ , there exists only one cycle $(11101, 11100, 11111, 11110)$ of length 4 containing the edge $e$ . If $F = {11100}$ or $F = {11111}$ , then there exists no fault-free cycle of length 4 containing the edge $e$ in $M Q_{5}^{1} - F$ .

For $ℓ = 5$ , in $M Q_{5}$ , taking $e = (11110, 11111)$ , the cycles of length 5 containing the edge $e$ are as $T a b l e 1$ and $T a b l e 2$ (we calculate it by computer):

Table 1 Cycles of length 5 containing the edge $e = (11110, 11111)$ in $M Q_{5}^{0}$
(11110 11101 11010 11000 11111)	(11110 11101 10010 10000 11111)
(11110 11001 11011 11100 11111)	(11110 10001 10011 11100 11111)

Table 2 Cycles of length 5 containing the edge $e = (11110, 11111)$ in $M Q_{5}^{0}$
(11110 11101 11010 11000 11111)	(11110 11101 10010 10000 11111)
(11110 11101 00010 00000 11111)	(11110 11001 11011 11100 11111)
(11110 10001 10011 11100 11111)	(11110 00001 00011 11100 11111)

If $F = {11100, 11101}$ , then there exists no fault-free cycle of length 5 containing the edge $e$ in $M Q_{5} - F$ .

For $ℓ = 6$ , in $M Q_{n}^{0}$ , taking $e = (01011, 01100)$ , the cycles of length 6 containing the edge $e$ are as $T a b l e 3$ (we calculate it by computer):

Table 3 Cycles of length 6 containing the vertex $e = (01011, 01100)$ in $M Q_{5}^{0}$
(01011 01010 01000 00000 00100 01100)	(01011 01010 01101 01110 01111 01100)
(01011 01010 01101 00101 00100 01100)	(01011 01010 01101 11101 11100 01100)
(01011 01010 00010 00000 00100 01100)	(01011 01010 11010 11011 11100 01100)
(01011 01010 11010 11101 11100 01100)	(01011 01010 11010 11101 01101 01100)
(01011 01001 01000 01010 01101 01100)	(01011 01001 01000 00000 00100 01100)
(01011 01001 00001 00000 00100 01100)	(01011 01001 00001 00101 00100 01100)
(01011 01001 00001 00101 01101 01100)	(01011 01001 11001 11011 11100 01100)
(01011 00011 00010 00000 00100 01100)	(01011 00011 00010 01010 01101 01100)
(01011 00011 00001 00000 00100 01100)	(01011 00011 00001 00101 00100 01100)
(01011 00011 00001 00101 01101 01100)	(01011 11011 11010 11101 11100 01100)
(01011 11011 11010 11101 01101 01100)	(01011 11011 11010 01010 01101 01100)
(01011 11011 11100 11101 01101 01100)	(01011 11011 11100 11111 01111 01100)

If $F = {00100, 01101, 11100}$ , then there exists no fault-free cycle of length 6 containing the edge $e$ in $M Q_{5}^{0} - F$ .

Acknowledgements

The research is supported by National Natural Science Foundation of China under Grant No.U22A2005, No. U21A20491, No. U1936109, No.U1908214, No. KLSA201906 and Key Research and Development Program of Zhejiang (2024SSYS0001).

References:

P. Cull and S. M. Larson. The möbius cubes. IEEE Transactions on Computers, 44(5):647–659, 1995.
J. X. Fan. Diagnosability of the möbius cubes. IEEE Transactions on Parallel and Distributed Systems, 9(9):923–928, 1998.
J. X. Fan. Hamilton-connectivity and cycle-embedding of the möbius cubes. Information Processing Letters, 82(2):113–117, 2002. https://doi.org/10.1016/S0020-0190(01)00256-3.
S. Y. Hsieh. Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges. Parallel Computing, 32(1):84–91, 2006. https://doi.org/10.1016/j.parco.2005.09.003.
S. Y. Hsieh and N. W. Chang. Hamiltonian path embedding and pancyclicity on the möbius cube with faulty nodes and faulty edges. IEEE Transactions on Computers, 55(7):854–863, 2006.
S. Y. Hsieh and C. H. Chen. Pancyclicity on möbius cubes with maximal edge faults. Parallel Computing, 30(3):407–421, 2004. https://doi.org/10.1016/j.parco.2003.12.003.
W. T. Huang, Y. C. Chuang, J. J. M. Tan, and L. H. Hsu. Fault-free Hamiltonian cycle in faulty möbius cubes. Journal of Computing Systems, 4:106–114, 2000.
J. Xu and Z. Deng. Wide diameter of möbius cubes. Journal of Interconnection Networks, 6(1):51–62, 2005. https://doi.org/10.1142/S0219265905001319.
J. M. Xu and M. J. Ma. Survey on path and cycle embedding in some networks. Frontiers of Mathematics in China, 4(2):217–252, 2009. https://doi.org/10.1007/s11464-009-0017-5.
J. M. Xu, M. J. Ma, and M. Lu. Paths in möbius cubes and crossed cubes. Information Processing Letters, 97(3):94–97, 2006. https://doi.org/10.1016/j.ipl.2005.09.015.
M. Xu and J. Xu. Edge-pancyclicity of möbius cubes. Information Processing Letters, 96(4):136–140, 2005. https://doi.org/10.1016/j.ipl.2005.07.003.
X. R. Xu, H. F. Zhang, and Y. S. Yang. Fault-tolerant edge-pancyclicity of möbius cubes MQn. In 2018 IEEE International Conference on Parallel and Distributed Processing with Applications, pages 237–243, Australia, 2018. https://doi.org/10.1109/BDCloud.2018.00046.
X. Yang and G. M. Megson. Fault tolerance of möbius cubes under two forbidden fault set models. International Journal of Computer Mathematics, 81(8):909–916, 2004. https://doi.org/10.1080/00207160410001712332.
H. F. Zhang, X. R. Xu, P. D. Soomro, and Y. S. Yang. Fault-tolerant Hamiltonian connectivity of twisted hypercube-like networks THLNs. IEEE Access, 6:74081–74090, 2018. https://doi.org/10.1109/ACCESS.2018.2882520.

[1] P. Cull and S. M. Larson. The möbius cubes. IEEE Transactions on Computers, 44(5):647–659, 1995.

[2] J. X. Fan. Diagnosability of the möbius cubes. IEEE Transactions on Parallel and Distributed Systems, 9(9):923–928, 1998.

[3] J. X. Fan. Hamilton-connectivity and cycle-embedding of the möbius cubes. Information Processing Letters, 82(2):113–117, 2002. https://doi.org/10.1016/S0020-0190(01)00256-3.

[4] S. Y. Hsieh. Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges. Parallel Computing, 32(1):84–91, 2006. https://doi.org/10.1016/j.parco.2005.09.003.

[5] S. Y. Hsieh and N. W. Chang. Hamiltonian path embedding and pancyclicity on the möbius cube with faulty nodes and faulty edges. IEEE Transactions on Computers, 55(7):854–863, 2006.

[6] S. Y. Hsieh and C. H. Chen. Pancyclicity on möbius cubes with maximal edge faults. Parallel Computing, 30(3):407–421, 2004. https://doi.org/10.1016/j.parco.2003.12.003.

[7] W. T. Huang, Y. C. Chuang, J. J. M. Tan, and L. H. Hsu. Fault-free Hamiltonian cycle in faulty möbius cubes. Journal of Computing Systems, 4:106–114, 2000.

[8] J. Xu and Z. Deng. Wide diameter of möbius cubes. Journal of Interconnection Networks, 6(1):51–62, 2005. https://doi.org/10.1142/S0219265905001319.

[9] J. M. Xu and M. J. Ma. Survey on path and cycle embedding in some networks. Frontiers of Mathematics in China, 4(2):217–252, 2009. https://doi.org/10.1007/s11464-009-0017-5.

[10] J. M. Xu, M. J. Ma, and M. Lu. Paths in möbius cubes and crossed cubes. Information Processing Letters, 97(3):94–97, 2006. https://doi.org/10.1016/j.ipl.2005.09.015.

[11] M. Xu and J. Xu. Edge-pancyclicity of möbius cubes. Information Processing Letters, 96(4):136–140, 2005. https://doi.org/10.1016/j.ipl.2005.07.003.

[12] X. R. Xu, H. F. Zhang, and Y. S. Yang. Fault-tolerant edge-pancyclicity of möbius cubes MQn. In 2018 IEEE International Conference on Parallel and Distributed Processing with Applications, pages 237–243, Australia, 2018. https://doi.org/10.1109/BDCloud.2018.00046.

[13] X. Yang and G. M. Megson. Fault tolerance of möbius cubes under two forbidden fault set models. International Journal of Computer Mathematics, 81(8):909–916, 2004. https://doi.org/10.1080/00207160410001712332.

[14] H. F. Zhang, X. R. Xu, P. D. Soomro, and Y. S. Yang. Fault-tolerant Hamiltonian connectivity of twisted hypercube-like networks THLNs. IEEE Access, 6:74081–74090, 2018. https://doi.org/10.1109/ACCESS.2018.2882520.

Contents

Ars Combinatoria

$(n - 2)$ -fault-tolerant edge-pancyclicity of möbius cubes $M Q_{n}$

Abstract

1. Introduction

2. Definitions and properties

3. Fault-tolerant edge-pancyclicity of $M Q_{n}$

4. Conclusion and remarks

Acknowledgements

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Ars Combinatoria

(n−2)-fault-tolerant edge-pancyclicity of möbius cubes MQn

Abstract

1. Introduction

2. Definitions and properties

3. Fault-tolerant edge-pancyclicity of MQn

4. Conclusion and remarks

Acknowledgements

References:

Information

Guidelines

CP Initiatives

Follow CP

$(n - 2)$ -fault-tolerant edge-pancyclicity of möbius cubes $M Q_{n}$

3. Fault-tolerant edge-pancyclicity of $M Q_{n}$