2-Disjoint-path-coverable panconnectedness of crossed cubes

Abstract

The crossed cube is a popular network topology because it possesses many attractive topological properties and its diameter is about half that of the hypercube. Typically, a network topology is modeled as a graph whose vertices and edges represent processors and communication links, respectively. We define a graph $G$ to be $2$-disjoint-path-coverably $r$-panconnected for a positive integer $r$ if for any four distinct vertices $u,\, v,\, x$, and $y$ of $G$, there exist two vertex-disjoint paths $P_1$ and $P_2,$ such that (i) $P_1$ joins $u$ and $v$ with length $l$ for any integer $l$ satisfying $r \le l \le |V(G)| - r - 2$, and (ii) $P_2$ joins $x$ and $y$ with length $|V(G)| - l - 2$, where $|V(G)|$ is the total number of vertices in $G$. This property can be considered as an extension of both panconnectedness and connectivity. In this paper, we prove that the $n$-dimensional crossed cube is $2$-disjoint-path-coverably $n$-panconnected.

1 Introduction

In parallel and distributed computer systems, multiprocessors are connected using various types of interconnection networks. A variety of interconnection mechanisms have been proposed during the last two decades to guarantee that system performance can achieve the desired level [29, 34, 42]. Historically, interconnection networks, such as multidimensional cubes and their variations, have been successfully applied to solve various hardware and software problems. For example, multidimensional cubes have been used in data modeling of multidimensional databases. All possible aggregations computed from a multidimensional database relation are stored in a data cube. A data cube can support online analytical processing (OLAP), which has gained popularity as a method for supporting decision making and can serve in a cloud-computing environment [22, 36, 39].

Among the many kinds of network topologies, the binary $n$-dimensional cube (or hypercube) is one of the most popular for parallel and distributed computation [40]. Not only is it ideally suited to both special- and general-purpose tasks, but it can also efficiently simulate many other network types [34]. In addition to the hypercube, reconfigurable networks [7, 11–13] and ring-based transputer networks [4, 5] offer cost-effective alternatives to the hypercube multiprocessor architecture without substantial loss in performance. In particular, parallel algorithms targeted at a reconfigurable network were developed for various imaging processing, pattern recognition, and computer vision tasks, such as edge detection in an image [10], rotation of digitized images [3, 6], and stereocorrelation [8, 9].

However, even though hypercube networks have many promising advantages, they are bipartite and do not have paths/cycles of many specified lengths. In addition, the hypercube has the largest diameter of the cube family. To compensate for these drawbacks, many researchers have tried to refashion a hypercube into others with lower diameters [1, 19, 23, 43]. One such network topology is the crossed cube, which was first proposed by Efe [24]. The crossed cube is derived from the hypercube by changing some link connections. Its diameter is about half that of the hypercube [15, 24]. In addition, the crossed cube has many other attractive properties. For example, it contains more cycles than the hypercube [27] and binary trees as subgraphs [32]. Moreover, paths of odd and even lengths can be embedded in the crossed cube [25, 26].

Typically, the topological structure of an interconnection network is modeled as a graph whose vertices and edges represent processors and communication links, respectively, and the representations for graphs in data structures are commonly adjacency matrix/lists. Global data structures extensively applied in the cube family include linear arrays, cyclic queues, trees, and meshes [34]. Thus, diverse approaches to embedding paths/cycles/trees/meshes in members of the cube family have been widely studied. A comprehensive survey of related work can be found in [29, 42]. Throughout this paper, graphs are finite, simple, and undirected. Some important graph-theory definitions and notations will be introduced first. For those not defined here, we follow the standard terminology given by Bondy and Murty [14]. An undirected graph $G$ is a graph with vertex set $V(G)$ and edge set $E(G)$, where $|V(G)|>0$ and $E(G) \subseteq \{ (u,v)|(u,v)$ is an unordered pair of elements of $V(G)$}. Two vertices $u$ and $v$ of $G$ are adjacent if $(u,v)\in E(G)$. A graph $H$ is a subgraph of $G$, denoted by $H \subseteq G$, if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$, and $H$ is a spanning subgraph of $G$ (equivalently, $H$ spans $G$) if $V(H)=V(G)$. Let $S$ be a nonempty subset of $V(G)$. The subgraph of $G$ induced by $S$ is a graph whose vertex set is $S$ and whose edge set consists of all the edges of $G$ joining any two vertices in $S$.

A path $P$ of length $k,\, k \ge 1$, from vertex $x$ to vertex $y$ in a graph $G$ is a sequence of distinct vertices $\langle v_1,v_2,\ldots ,v_{k+1}\rangle ,$ such that $v_1=x,\, v_{k+1}=y$, and $(v_i,v_{i+1}) \in E(G)$ for every $i,\, 1 \le i \le k$. Moreover, a path of length zero, consisting of a single vertex $x$, is denoted by $\langle x\rangle$. We can write $P$ as $\langle v_1,v_2,\ldots ,v_i,Q,v_j,\ldots ,v_{k+1}\rangle$ for convenience if $Q \subset P$ and $Q=\langle v_i,\ldots ,v_j\rangle$, where $i \le j$. The $i\mathrm{th}$ vertex of $P$ is denoted by $P(i)$, i.e., $P(i)=v_i$. In particular, let $\mathrm{rev}(P)$ represent the reverse of $P$, i.e., $\mathrm{rev}(P)=\langle v_{k+1},v_{k},\ldots ,v_1\rangle$. We use $l(P)$ to denote the length of $P$. The distance between two distinct vertices $u$ and $v$ in $G$, denoted by $d_G(u,v)$, is the length of the shortest path between $u$ and $v$. The diameter of $G$ is the maximum of all shortest paths for all pairs of vertices in $G$. Furthermore, $G$ is connected if there are paths joining every pair of distinct vertices in $G$; otherwise, $G$ is disconnected or trivial. The connectivity $\kappa (G)$ of a connected graph $G$ is the minimum number of vertices whose removal from $G$ results in a disconnected or trivial graph. We say that $G$ is n-connected if $\kappa (G) \ge n \ge 1$. A cycle is a path with at least three vertices, such that the last vertex is adjacent to the first one. For clarity, a cycle of length $k,\, k \ge 3$, is represented as $\langle v_1,v_2,\ldots ,v_k,v_1\rangle$ and denoted by $C_k$. A path (respectively, cycle) is a Hamiltonian path (respectively, Hamiltonian cycle) of $G$ if it spans $G$. We say that $G$ is Hamiltonian if it has a Hamiltonian cycle, and that $G$ is Hamiltonian-connected if it contains a Hamiltonian path joining any pair of distinct vertices.

A many-to-many k-disjoint path cover ($k$-DPC) of a graph $G$ is a set of $k$ vertex-disjoint paths joining $k$ sources and $k$ sinks, in which each vertex of $G$ is covered by a path [37]. The problem of finding a $k$-DPC in a graph can be further addressed from different perspectives of combinatorial optimization. For example, the maximum weight disjoint-path cover problem is to find a disjoint-path cover of a weighted graph $G,$ such that the total weight of these paths is maximized [35]. For another example, Wu and Manber [41] discussed the problem of finding disjoint-path covers (called perfect path matching in their work) with constraints on the maximum length of paths. Cohen et al. applied this problem in the study of optimized broadcasting and multicasting protocols in networks, basing their approaches to connecting a given set of vertices on finding a set of edge-disjoint paths [20] and vertex-disjoint paths [21], respectively. To reduce broadcast delay, one approach is to address length-constrained path matching. In [28], Ghodsi et al. studied the length-constrained path-matching problem for general graphs. For these reasons, we are motivated to explore all possible path lengths of a $k$-DPC. Obviously, the problem of finding a $1$-DPC is equivalent to the problem of finding a Hamiltonian path, which is known to be NP-complete. For $k \ge 2$, the embedding of a $k$-DPC can be achieved in the crossed cube and some other hypercube variations [37, 38]. However, owing to potential difficulties in controlling the lengths of a $k$-DPC for any $k \ge 2$, we focus on the $2$-DPC problem as our first milestone. Previous work [33] showed that there exists a $2$-DPC in a crossed cube whose vertex-disjoint paths have the same length. In this paper, we improve on this result, enabling the path lengths of a $2$-DPC in the crossed cube to meet all possibilities. To be precise, we need to introduce the definition of panconnectedness and propose a new concept, “$2$-DPC panconnectedness”.

A graph $G$ is panconnected if for any two distinct vertices $x$ and $y$, it contains a path of length $l$ joining $x$ and $y$ for any integer $l$ satisfying $d_G(x,y) \le l \le |V(G)|-1$ [2]. According to the above definition, we can define a graph $G$ to be 2-disjoint-path-coverably r-panconnected (or $2$-DPC $r$-panconnected for short) for a positive integer $r$ if for any four distinct vertices $u$, $v$, $x$, and $y$ of $G$, there exist two vertex-disjoint paths $P_1$ and $P_2,$ such that (i) $P_1$ joins $u$ and $v$ with length $l$ for any integer $l$ satisfying $r \le l \le |V(G)| - r - 2$, and (ii) $P_2$ joins $x$ and $y$ with length $|V(G)| - l - 2$. In this paper, we investigate all aspects of $2$-DPC $r$-panconnectedness with respect to the crossed cube.

The remainder of this paper is organized as follows. In Sect. 2, we introduce the definition and some useful properties of the crossed cube. The main theorem and the proof are described in Sect. 3. Concluding remarks are provided in Sect. 4.

2 The crossed cube and its properties

The $n$-dimensional crossed cube, denoted by $CQ_n$, contains $2^n$ vertices, each of which corresponds to an $n$-bit binary string. To define the crossed cube, we need to first introduce an additional concept, “pair related”.

Definition 1

[24] Two $2$-bit binary strings $\mathbf {x} = x_2 x_1$ and $\mathbf {y} = y_2 y_1$ are pair related, denoted by $\mathbf {x} \sim \mathbf {y}$, if and only if $(\mathbf {x}, \mathbf {y}) \in \{(00,00), (10,10), (01,11), (11,01)\}$.

The formal definition of $CQ_n$ is given below.

Definition 2

[24] The $n$-dimensional crossed cube $CQ_n$ is recursively constructed as follows:

• (i) $CQ_1$ is a complete graph with vertex set $\{0, 1\}$.

• (ii) $CQ_2$ is isomorphic to a $C_4$ with vertex set $\{00, 01, 10, 11\}$ and edge set $\{ (00, 01)$, $(00, 10)$, $(10, 11)$, $(01, 11) \}$.

• (iii) For $n \ge 3$, let $CQ^0_{n-1}$ and $CQ^1_{n-1}$ be two copies of $CQ_{n-1}$ with $V(CQ^0_{n-1}) = \{0u_{n-1}u_{n-2} \ldots u_1 \mid u_i = 0 \hbox { or } 1 \hbox { for } 1 \le i \le n-1\}$ and $V(CQ^1_{n-1}) = \{1u_{n-1}u_{n-2} \ldots u_1 \mid u_i = 0 \hbox { or } 1 \hbox { for } 1 \le i \le n-1\}$. Then, $CQ_n$ is formed by connecting $CQ^0_{n-1}$ and $CQ^1_{n-1}$ with $2^{n-1}$ edges, so that a vertex $\mathbf {u} = 0u_{n-1}u_{n-2} \ldots u_1$ of $CQ^0_{n-1}$ is adjacent to a vertex $\mathbf {v} = 1v_{n-1}v_{n-2} \ldots v_1$ of $CQ^1_{n-1}$ if and only if (1) $u_{n-1} = v_{n-1}$ when $n$ is even, and (2) $u_{2i}u_{2i-1} \sim v_{2i}v_{2i-1}$ for all $i,\, 1 \le i \le \left\lfloor \frac{n-1}{2}\right\rfloor$. $CQ^0_{n-1}$ and $CQ^1_{n-1}$ are subcubes of $CQ_n$.

Figure 1 depicts $CQ_3$ and $CQ_4$. It has been proved that $CQ_n$ is $n$-connected [31] and has diameter $\left\lceil \frac{n+1}{2} \right\rceil$ [24].

Fig. 1

Illustration of $CQ_3$ and $CQ_4$

A vertex $\mathbf {u} = u_{n} u_{n-1} \ldots u_{1}$ of $CQ_n$ is said to be adjacent to a vertex $\mathbf {v} = v_{n} v_{n-1} \ldots v_{1}$ along the $i\mathrm{th}$ dimension, $1\le i \le n$, if the following four conditions are all satisfied: (i) $u_i \ne v_i$, (ii) $u_j = v_j$ for all $j,\, i+1 \le j \le n$, (iii) $u_{2k} u_{2k-1} \sim v_{2k} v_{2k-1}$ for all $k,\, 1 \le k \le \left\lfloor \frac{i-1}{2}\right\rfloor$, and (iv) $u_{i-1} = v_{i-1}$ if $i$ is even. Then, we say that $\mathbf {u}$ is the i-neighbor of $\mathbf {v}$, denoted by $(\mathbf {v})^i$, and vice versa. The edge $(\mathbf {u},(\mathbf {u})^i)$ is called an i-dimensional edge. It is easy to see that $\mathbf {v} = (\mathbf {u})^i$ if and only if $\mathbf {u} = (\mathbf {v})^i$.

The following lemma provides the basis for a method proposed by Chen et al. for finding a $C_4$ with an $n$-dimensional edge of $CQ_n$ [17].

Lemma 1

[17] Let $(\mathbf {u}, \mathbf {v})$ be any $n$-dimensional edge of $CQ_n,\, n \ge 3$. For any integer $i,\, 1 \le i \le n - 1$, vertices $\mathbf {u},\, \mathbf {v},\, (\mathbf {u})^i$, and $(\mathbf {v})^i$ induce a $C_4$ if $i$ is even or $i = n - 1$.

In [27], Fan et al. described how to locate a $C_5$ in $CQ_n$.

Lemma 2

[27] Let $(\mathbf {u}, \mathbf {v})$ be any $n$-dimensional edge of $CQ_n,\, n \ge 3$. Then, $((\mathbf {u})^1)^n = ((\mathbf {v})^2)^1 = ((\mathbf {v})^1)^2$. Moreover,

• (i) vertices $\mathbf {u},\, \mathbf {v},\, (\mathbf {u})^1,\, (\mathbf {v})^2$, and $((\mathbf {v})^{2})^{1}$ induce a $C_5$, and

• (ii) vertices $\mathbf {u},\, \mathbf {v},\, (\mathbf {u})^1,\, (\mathbf {v})^1$, and $((\mathbf {v})^{1})^{2}$ induce a $C_5$.

Let $F$ be a subgraph of $G$, and let $G-F$ denote the removal of $F$ from $G$. A Hamiltonian graph $G$ is f-fault-tolerant Hamiltonian (respectively, f-fault-tolerant Hamiltonian-connected) if $G-F$ remains Hamiltonian (respectively, Hamiltonian-connected) for every $F$ with $|F| \le f$, where $|F|$ is the number of all vertices and edges in $F$.

Lemma 3

[30] For any integer $n,\, n \ge 3,\, CQ_n$ is $(n - 2)$-fault-tolerant Hamiltonian and $(n - 3)$-fault-tolerant Hamiltonian-connected.

Hereafter, we discuss some properties regarding fault-tolerance of $CQ_n$.

Lemma 4

Let $F$ be a subset of $V(CQ_n)$, where $n \ge 5$ and $0 \le |F| \le n$. In addition, let $F_0 = F \cap V(CQ^0_{n-1})$ and $F_1 = F \cap V(CQ^1_{n-1})$. If both $CQ^0 _{n-1} - F_0$ and $CQ^1_{n-1} - F_1$ are Hamiltonian-connected, then $CQ_n - F$ is also Hamiltonian-connected. Moreover, for any two vertices $\mathbf {u}$ and $\mathbf {v}$ of $CQ_n - F$, there exists a Hamiltonian path $P$ in $CQ_n - F$ joining $\mathbf {u}$ and $\mathbf {v},$ such that $P$ contains a Hamiltonian path of $CQ^0_{n-1} - F_0$ or a Hamiltonian path of $CQ^1_{n-1} - F_1$ as its subpath.

Proof

Without loss of generality, assume $\mathbf {u} \in V(CQ^0_{n-1})$. Consider the following two cases.

Case 1. $\mathbf {v} \in V(CQ^0_{n-1}) - F_0$. Let $R$ be a Hamiltonian path of $CQ^0_{n-1} - F_0$ joining $\mathbf {u}$ and $\mathbf {v}$. For convenience, we write $R$ as $\langle \mathbf {u}, R_1, \mathbf {x}, \mathbf {y}, R_2, \mathbf {v}\rangle$ for some vertices $\mathbf {x}$ and $\mathbf {y}$, where $\{(\mathbf {x})^n, (\mathbf {y})^n\} \cap F_1 = \emptyset$. Note that we can find such $\mathbf {x}$ and $\mathbf {y}$ because $|V(CQ^0_{n-1}) - F_0 - \{\mathbf {u}, \mathbf {v}\}| \ge 2^{n-1} - n - 2$ and $|F_1| \le n$. Let $S$ be a Hamiltonian path of $CQ^1_{n-1} - F_1$ joining $(\mathbf {x})^n$ and $(\mathbf {y})^n$. Then, path $P = \langle \mathbf {u}, R_1, \mathbf {x}, (\mathbf {x})^n, S, (\mathbf {y})^n, \mathbf {y}, R_2, \mathbf {v}\rangle$ is a Hamiltonian path of $CQ_n - F$ joining $\mathbf {u}$ and $\mathbf {v}$ with $S \subset P$.

Case 2. $\mathbf {v} \in V(CQ^1_{n-1}) - F_1$. Let $R$ be a Hamiltonian path of $CQ^0_{n-1} - F_0$ joining $\mathbf {u}$ and some vertex $\mathbf {z}$ of $CQ^0_{n-1} - (F_0 \cup \{\mathbf {u}\})$, where $(\mathbf {z})^n \not \in \{\mathbf {v}\} \cup F_1$. Moreover, let $S$ be a Hamiltonian path of $CQ^1_{n-1} - F_1$ joining $(\mathbf {z})^n$ and $\mathbf {v}$. Then, $P = \langle \mathbf {u}, R, \mathbf {z}, (\mathbf {z})^n, S, \mathbf {v}\rangle$ is a Hamiltonian path of $CQ_n - F$ joining $\mathbf {u}$ and $\mathbf {v}$ with $R \subset P$ and $S \subset P$. $\square$

Lemma 5

Let $\mathbf {u}$ be any vertex of $CQ_n$ and $(\mathbf {x}, \mathbf {y})$ any edge of $CQ_n - \{\mathbf {u}\},\, n \ge 5$. Then, $CQ_n - \{\mathbf {u}, \mathbf {x}, \mathbf {y}\}$ is Hamiltonian-connected.

Proof

By brute force, running our computer program [16], we can verify that $CQ_5 - \{\mathbf {u}, \mathbf {x}, \mathbf {y}\}$ is Hamiltonian-connected. For $n \ge 6,\, CQ_n - \{\mathbf {u}, \mathbf {x}, \mathbf {y}\}$ is Hamiltonian-connected by Lemma 3. $\square$

Lemma 6

Let $(\mathbf {u}, \mathbf {v})$ and $(\mathbf {x}, \mathbf {y})$ be any two vertex-disjoint edges of $CQ_n,\, n \ge 5$. Then, $CQ_n - \{\mathbf {u}, \mathbf {v}, \mathbf {x}, \mathbf {y}\}$ is Hamiltonian-connected.

Proof

For $n = 5$, we can verify correctness by brute force running of our computer program [16]. For $n \ge 7$, Lemma 3 states that $CQ_n$ is at least $4$-fault-tolerant Hamiltonian-connected. Here, we need to show correctness for $CQ_6$. Let $F = \{\mathbf {u}, \mathbf {v}, \mathbf {x}, \mathbf {y}\}$. Moreover, let $F_0 = F \cap V(CQ^0_5)$ and $F_1 = F \cap V(CQ^1_5)$. Without loss of generality, assume $|F_0| \ge |F_1|$. Consider the following three cases.

Case 1. $|F_0| = 4$ and $|F_1| = 0$. As mentioned above for $n = 5,\, CQ^0_5 - F_0$ is Hamiltonian-connected. Because $CQ^1_5$ is also Hamiltonian-connected, $CQ_6 - F$ is Hamiltonian-connected by Lemma 4.

Case 2. $|F_0| = 3$ and $|F_1| = 1$. It is obvious that $F_0$ contains one vertex and two adjacent vertices. By Lemma 5, $CQ^0_5 - F_0$ is Hamiltonian-connected. By Lemma 3, $CQ^1_5 - F_1$ is also Hamiltonian-connected. Thus, $CQ_6 - F$ is Hamiltonian-connected.

Case 3. $|F_0| = 2$ and $|F_1| = 2$. By Lemma 3, both $CQ^0_5 - F_0$ and $CQ^1_5 - F_1$ are Hamiltonian-connected. Then, $CQ_6 - F$ is Hamiltonian-connected. $\square$

Lemma 7

[18] Let $F$ be any path of length $m,\, m \le n - 2$, in $CQ_n$ for $n \ge 5$. Then, $CQ_n - V(F)$ is Hamiltonian-connected.

Let $( \mathbf {u}, \mathbf {v} )$ be an $i$-dimensional edge of $CQ_n$ for any $i,\, 1 \le i \le n$. $(\mathbf {u}, \mathbf {v})$ is an even edge, if $i$ is even.

Lemma 8

Let $F$ be a path of length one or two in $CQ_n$ for $n \ge 5$. There exists a Hamiltonian path $P$ in $CQ_n - F$ joining any two vertices and $P$ has at least four vertex-disjoint even edges.

Proof

We prove this lemma by induction. By brute force running of our computer programs [16], we can verify the validity of the induction base on $CQ_5$. The inductive hypothesis is that the statement holds for all $CQ_k,\, 5 \le k \le n - 1$. We show that the statement also holds for $CQ_n$. Let $F_0 = V(F) \cap V(CQ^0_{n-1})$ and $F_1 = V(F) \cap V(CQ^1_{n-1})$. Without loss of generality, assume $|F_0| \ge |F_1|$. Then, we have the following cases: (1) $|F_0| = 3$ and $|F_1| = 0$, (2) $|F_0| = 2$ and $|F_1| = 1$, (3) $|F_0| = 2$ and $|F_1| = 0$, and (4) $|F_0| = 1$ and $|F_1| = 1$. In each of the above cases, both $CQ^0_{n-1} - F_0$ and $CQ^1_{n-1} - F_1$ are Hamiltonian-connected, and $CQ_n - F$ is Hamiltonian-connected. By the inductive hypothesis, we have a Hamiltonian path $R$ (respectively, $S$) joining any two vertices in $CQ^0_{n-1} - F_0$ (respectively, $CQ^1_{n-1} - F_1$) that contains at least four vertex-disjoint even edges. Then, by Lemma 4, there exists a Hamiltonian path $P$ in $CQ_n - F$ joining any two vertices, such that $P$ contains $R$ or $S$ as a subpath, and $P$ has at least four vertex-disjoint even edges. $\square$

Lemmas 9 and 10 discuss some properties regarding embedding paths of required lengths in $CQ_n$.

Lemma 9

[17] Let $\mathbf {u}$ and $\mathbf {v}$ be any two vertices of $CQ_n$, $n \ge 4$. Moreover, let $l$ be any integer with $d_{CQ_n}(\mathbf {u}, \mathbf {v}) \le l \le 2^n - 1$ and $l \ne d_{CQ_n}(\mathbf {u}, \mathbf {v}) + 1$. There exists a Hamiltonian path $P$ of $CQ_n,$ such that $P(1) = \mathbf {u}$ and $P(l + 1) = \mathbf {v}$.

Lemma 10

Let $\mathbf {w}$ be any vertex of $CQ_n$, $n \ge 5$. Moreover, let $\mathbf {u}$ and $\mathbf {v}$ be any two vertices of $CQ_n - \{\mathbf {w}\}$. There exists a path of length $l$, $l \in \{n-1, n, n+1\}$, joining $\mathbf {u}$ and $\mathbf {v}$ in $CQ_n - \{\mathbf {w}\}$.

Proof

Without loss of generality, assume $\mathbf {w} \in V(CQ^0_{n-1})$. Moreover, assume $\mathbf {u} \in V(CQ^0_{n-1})$ if $\mathbf {u}$ and $\mathbf {v}$ are in different subcubes. The inductive proof proceeds as follows. By brute force running of our computer program [16], we verify that the statement holds for $n = 5$. The inductive hypothesis assumes that this lemma holds for $CQ_{n-1}$ if $n \ge 6$. Consider the following three cases.

Case 1. $\{\mathbf {u}, \mathbf {v}\} \subset V(CQ^0_{n-1}) - \{\mathbf {w}\}$. By the inductive hypothesis, we can find a path of length $m$, $m \in \{n-1, n\}$ in $CQ^0_{n-1} - \{\mathbf {w}\}$ joining $\mathbf {u}$ and $\mathbf {v}$. This path is certainly a path of $CQ_n - \{\mathbf {w}\}$. Because $n \ge 6$, we have $\left\lceil \frac{(n-1)+1}{2} \right\rceil + 2 \le n - 1$, which implies that $d_{CQ^1_{n-1}}((\mathbf {u})^n, (\mathbf {v})^n) + 2 \le n-1$. By Lemma 9, there exists a path $S$ of length $n - 1$ in $CQ^1_{n-1}$ joining $(\mathbf {u})^n$ and $(\mathbf {v})^n$, and $\langle \mathbf {u}, (\mathbf {u})^n, S, (\mathbf {v})^n, \mathbf {v}\rangle$ is a path of length $n+1$ in $CQ_n - \{\mathbf {w}\}$ joining $\mathbf {u}$ and $\mathbf {v}$.

Case 2. $\{\mathbf {u}, \mathbf {v}\} \subset V(CQ^1_{n-1})$. Because $n \ge 6$ and $\left\lceil \frac{(n-1)+1}{2} \right\rceil + 2 \le n - 1$, we have a path of length $m,\, m \in \{n-1, n, n+1\}$ in $CQ^1_{n-1}$ joining $\mathbf {u}$ and $\mathbf {v}$ by Lemma 9. Certainly, such a path is also a path of $CQ_n - \{\mathbf {w}\}$.

Case 3. $\mathbf {u} \in V(CQ^0_{n-1}) - \{\mathbf {w}\}$ and $\mathbf {v} \in V(CQ^1_{n-1})$. The following two subcases are distinguished.

Subcase 3.1. $(\mathbf {u})^n \ne \mathbf {v}$. Let $\mathbf {x} \in V(CQ^1_{n-1}) - \{(\mathbf {u})^n,\mathbf {v}\}$. By the inductive hypothesis, there exists a path $S$ of length $m$, $m \in \{n-2, n-1, n\}$, in $CQ^1_{n-1} - \{\mathbf {x}\}$ joining $(\mathbf {u})^n$ and $\mathbf {v}$. Then, $\langle \mathbf {u}, (\mathbf {u})^n, S, \mathbf {v}\rangle$ is a path of $CQ_n - \{\mathbf {w}\}$ with length $m$, $m \in \{n-1, n, n+1\}$.

Subcase 3.2. $(\mathbf {u})^n = \mathbf {v}$. Let $\mathbf {x} = (\mathbf {u})^i$ be a vertex of $CQ^0_{n-1} - \{\mathbf {w}\}$ with $i$ even. Then, vertices $\mathbf {u}$, $\mathbf {x}$, $(\mathbf {x})^n$, and $\mathbf {v}$ form a $C_4$. Because $n \ge 6$, by Lemma 9, there exists a path $S$ of length $m$, $m \in \{n-3, n-2, n-1\}$, in $CQ^1_{n-1}$ joining $(\mathbf {x})^n$ and $\mathbf {v}$. Then, $\langle \mathbf {u}, \mathbf {x}, (\mathbf {x})^n, S, \mathbf {v}\rangle$ is a path of $CQ_n - \{\mathbf {w}\}$ with length $m$, $m \in \{n-1, n, n+1\}$. $\square$

3 2-DPC $n$-panconnectedness of $CQ_n$

In this section, we discuss the $2$-DPC $r$-panconnectedness of the crossed cube with two vertex-disjoint paths $P_1$ and $P_2$, where $P_1$ joins $\mathbf {u}$ and $\mathbf {v}$, and $P_2$ joins $\mathbf {x}$ and $\mathbf {y}$ for any four vertices $\mathbf {u},\, \mathbf {v},\, \mathbf {x}$ and $\mathbf {y}$. In [33], it is shown that $CQ_3$ and $CQ_4$ will not have $2$-DPCs of equal length when vertex pairs $(\mathbf {u}, \mathbf {v})$ and $(\mathbf {x}, \mathbf {y})$ in $CQ_3$ (respectively, $CQ_4$) are $(000, 001)$ and $(010, 011)$ (respectively, $(0000, 0001)$ and $(0010, 1110)$). This implies that $CQ_3$ and $CQ_4$ are not $2$-DPC $r$-panconnected for any positive integer $r$. In our search result on $CQ_5$, if vertices $\mathbf {u},\, \mathbf {v},\, \mathbf {x}$, and $\mathbf {y}$ form a $C_4$ with $\mathbf {v} = (\mathbf {u})^2,\, \mathbf {x} = (\mathbf {u})^1$, and $\mathbf {y} = ((\mathbf {u})^1)^2$, then we cannot find any path of length four in $CQ_5 - \{\mathbf {u}, \mathbf {v}\}$ joining $\mathbf {x}$ and $\mathbf {y}$. Consequently, we will prove that $CQ_n$ is 2-DPC $n$-panconnected for $n \ge 5$ in the following theorem.

Theorem 1

Let $\mathbf {u},\, \mathbf {v},\, \mathbf {x}$, and $\mathbf {y}$ be any four vertices of $CQ_n,\, n \ge 5$. Moreover, let $l_1$ and $l_2$ be any two integers with $l_1 + l_2 = 2^n - 2,\, l_1 \ge n$, and $l_2 \ge n$. There exist two vertex-disjoint paths $P_1$ and $P_2$ in $CQ_n,$ such that (i) $P_1$ joins $\mathbf {u}$ and $\mathbf {v}$ with $l(P_1) = l_1$, and (ii) $P_2$ joins $\mathbf {x}$ and $\mathbf {y}$ with $l(P_2) = l_2$.

Proof

We prove this theorem by induction. First, we can show the validity of the induction base on $CQ_5$ by brute force running of our computer program [16]. The inductive hypothesis is that this theorem holds for all $CQ_k,\, 5 \le k \le n - 1$. Then, we show that this theorem also holds for $CQ_n$. Without loss of generality, assume $\mathbf {u} \in V(CQ^0_{n-1})$ and $l_1 \ge l_2$, i.e., $l_1 \ge 2^{n-1}-1$ and $l_2 \le 2^{n-1}-1$. Moreover, we assume $\mathbf {x} \in V(CQ^0_{n-1})$ if $\mathbf {x}$ and $\mathbf {y}$ are in different subcubes. We demonstrate all values of $l_2$. Consider the following six cases.

Case 1. $\{\mathbf {u}, \mathbf {v}, \mathbf {x}, \mathbf {y}\} \subset V(CQ^0_{n-1})$. Two subcases should be considered.

Subcase 1.1. $2^{n-2}+n-1 \le l_2 \le 2^{n-1}-1$. By the inductive hypothesis, there exist two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $\mathbf {v}$ with $l(R_1) = 2^{n-2} - 1$, and (ii) $R_2$ joins $\mathbf {x}$ and $\mathbf {y}$ with $l(R_2) = 2^{n-2} - 1$. We can write $R_1$ and $R_2$ as $\langle \mathbf {u}, R^1_1, \mathbf {a}, \mathbf {b}, R^2_1, \mathbf {v}\rangle$ and $\langle \mathbf {x}, R^1_2, \mathbf {p}, \mathbf {q}, R^2_2, \mathbf {y}\rangle$, respectively, for some vertices $\mathbf {a},\, \mathbf {b},\, \mathbf {p}$, and $\mathbf {q}$. Also by the inductive hypothesis, there exist two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $(\mathbf {b})^n$ with $l(S_1) = 2^{n-1} + 2^{n-2} - l_2 - 2$, and (ii) $S_2$ joins $(\mathbf {p})^n$ and $(\mathbf {q})^n$ with $l(S_2) = l_2 - 2^{n-2}$. We set $P_1 = \langle \mathbf {u}, R^1_1, \mathbf {a}, (\mathbf {a})^n, S_1, (\mathbf {b})^n, \mathbf {b}, R^2_1, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, R^1_2, \mathbf {p}, (\mathbf {p})^n, S_2, (\mathbf {q})^n, \mathbf {q}, R^2_2, \mathbf {y}\rangle$. Then, $P_1$ and $P_2$ are the required paths. See Fig. 2a for illustration.

Fig. 2

Case 1 in the proof of Theorem 1 (a dashed line or a straight line represents an edge)

Fig. 3

Case 2 in the proof of Theorem 1 (a dashed line or a straight line represents an edge)

Subcase 1.2. $n \le l_2 \le 2^{n-2} + n - 2$. By the inductive hypothesis, there exist two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $\mathbf {v}$ with $l(R_1) = 2^{n-1} - l_2 - 2$, and (ii) $R_2$ joins $\mathbf {x}$ and $\mathbf {y}$ with $l(R_2) = l_2$. We can write $R_1$ as $\langle \mathbf {u}, R^1_1, \mathbf {a}, \mathbf {b}, R^2_1, \mathbf {v}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b}$. By Lemma 3, there exists a Hamiltonian path $S$ of $CQ^1_{n-1}$ joining $(\mathbf {a})^n$ and $(\mathbf {b})^n$. We set $P_1 = \langle \mathbf {u}, R^1_1, \mathbf {a}, (\mathbf {a})^n, S, (\mathbf {b})^n, \mathbf {b}, R^2_1, \mathbf {v}\rangle$ and $P_2 = R_2$. It is obvious that $P_1$ and $P_2$ are the required paths. See Fig. 2b for illustration.

Case 2. $\{\mathbf {u}, \mathbf {x}, \mathbf {y}\} \subset V(CQ^0_{n-1})$ and $\mathbf {v} \in V(CQ^1_{n-1})$. Let $\mathbf {a}$ be a vertex of $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {x}, \mathbf {y}\}$ with $(\mathbf {a})^n \ne \mathbf {v}$. Consider the following two subcases.

Subcase 2.1. $2^{n-2} + n - 1 \le l_2 \le 2^{n-1} - 1$. By the inductive hypothesis, we have two vertex-disjoint paths $R_1$ and $R_2$ of $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $\mathbf {a}$ with $l(R_1) = 2^{n-2} - 1$, and (ii) $R_2$ joins $\mathbf {x}$ and $\mathbf {y}$ with $l(R_2) = 2^{n-2} - 1$. Path $R_2$ can be written as $\langle \mathbf {x}, R^1_2, \mathbf {p}, \mathbf {q}, R^2_2, \mathbf {y}\rangle$ for some vertices $\mathbf {p}$ and $\mathbf {q}$ with $\mathbf {v} \not \in \{(\mathbf {p})^n, (\mathbf {q})^n\}$. Also by the inductive hypothesis, we have two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $\mathbf {v}$ with $l(S_1) = 2^{n-1} + 2^{n-2} - l_2 - 2$, and (ii) $S_2$ joins $(\mathbf {p})^n$ and $(\mathbf {q})^n$ with $l(S_2) = l_2 - 2^{n-2}$. Then, $P_1 = \langle \mathbf {u}, R_1, \mathbf {a}, (\mathbf {a})^n, S_1, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, R^1_2, \mathbf {p}, (\mathbf {p})^n, S_2, (\mathbf {q})^n, \mathbf {q}, R^2_2, \mathbf {y}\rangle$ are our required paths. Figure 3a shows this subcase.

Subcase 2.2. $n \le l_2 \le 2^{n-2} + n - 2$. By the inductive hypothesis, we can find two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $\mathbf {a}$ with $l(R_1) = 2^{n-1} - l_2 - 2$, and (ii) $R_2$ joins $\mathbf {x}$ and $\mathbf {y}$ with $l(R_2) = l_2$. Because there exists a Hamiltonian path $S$ in $CQ^1_{n-1}$ joining $(\mathbf {a})^n$ and $\mathbf {v}$, we can set $P_1 = \langle \mathbf {u}, R_1, \mathbf {a}, (\mathbf {a})^n, S, \mathbf {v}\rangle$ and $P_2 = R_2$. Then, $P_1$ and $P_2$ are our required paths. Figure 3b shows this subcase.

Fig. 4

Case 3 in the proof of Theorem 1 (a dashed line or a straight line represents an edge)

Case 3. $\{\mathbf {u}, \mathbf {v}\} \subset V(CQ^0_{n-1})$ and $\{\mathbf {x}, \mathbf {y}\} \subset V(CQ^1_{n-1})$. The following subcases are distinguished.

Subcase 3.1. $l_2 = 2^{n-1} - 1$. Obviously, we have a Hamiltonian path $P_1$ of $CQ^0_{n-1}$ joining $\mathbf {u}$ and $\mathbf {v}$ and a Hamiltonian path $P_2$ of $CQ^1_{n-1}$ joining $\mathbf {x}$ and $\mathbf {y}$. Then, $P_1$ and $P_2$ are the required paths.

Subcase 3.2. $l_2 = 2^{n-1} - 2$. Because $n \ge 6$, by Lemma 2, we can find a neighbor $\mathbf {a}$ of $\mathbf {u}$ in $CQ^0_{n-1},$ such that $\{\mathbf {a}, \mathbf {b}, (\mathbf {b})^1, ((\mathbf {b})^1)^2, (\mathbf {a})^1\}$ induces a $C_5$ and $\{\mathbf {a}, \mathbf {b}, (\mathbf {b})^1, ((\mathbf {b})^1)^2, (\mathbf {a})^1\} \cap \{\mathbf {u}, \mathbf {v}, \mathbf {x}, \mathbf {y}\} = \emptyset$, where $\mathbf {b} = (\mathbf {a})^n$. By Lemma 8, there exists a Hamiltonian path $S$ in $CQ^1_{n-1} - \{\mathbf {b}, (\mathbf {b})^1, ((\mathbf {b})^1)^2\}$ joining $\mathbf {x}$ and $\mathbf {y},$ such that $S$ has at least four vertex-disjoint even edges. Among these even edges, we can find one even edge $(\mathbf {p}, \mathbf {q})$ such that $\{(\mathbf {p})^n, (\mathbf {q})^n\} \cap \{\mathbf {u}, \mathbf {v}\} = \emptyset$. It is noticed that $((\mathbf {p})^n, (\mathbf {q})^n) \in E(CQ_n)$. Path $S$ can be written as $\langle \mathbf {x}, S_1, \mathbf {p}, \mathbf {q}, S_2, \mathbf {y}\rangle$. By Lemma 6, there exists a Hamiltonian path $R$ in $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {a}, (\mathbf {p})^n, (\mathbf {q})^n\}$ joining $(\mathbf {a})^1$ and $\mathbf {v}$. Then, $P_1 = \langle \mathbf {u}, \mathbf {a}, \mathbf {b}, (\mathbf {b})^1, ((\mathbf {b})^1)^2, (\mathbf {a})^1, R, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, S_1, \mathbf {p}, (\mathbf {p})^n, (\mathbf {q})^n, \mathbf {q}, S_2, \mathbf {y}\rangle$ are the required paths. See Fig. 4a for illustration.

Subcase 3.3. $l_2 = 2^{n-1} - 3$. Let $\mathbf {a}$ and $\mathbf {b}$ be any two adjacent vertices of $CQ^1_{n-1} - \{\mathbf {x}, \mathbf {y}\},$ such that $\{\mathbf {u}, \mathbf {v}\} \cap \{(\mathbf {a})^n, (\mathbf {b})^n\} = \emptyset$. By the inductive hypothesis, we can find two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $(\mathbf {a})^n$ with $l(R_1) = 2^{n-2} - 1$, and (ii) $R_2$ joins $(\mathbf {b})^n$ and $\mathbf {v}$ with $l(R_2) = 2^{n-2} - 1$. By Lemma 3, there exists a Hamiltonian path $S$ in $CQ^1_{n-1} - \{\mathbf {a}, \mathbf {b}\}$ joining $\mathbf {x}$ and $\mathbf {y}$. We set $P_1 = \langle \mathbf {u}, R_1, (\mathbf {a})^n, \mathbf {a}, \mathbf {b}, (\mathbf {b})^n, R_2, \mathbf {v}\rangle$ and set $P_2 = S$. Then, $P_1$ and $P_2$ are the required paths. Figure 4b illustrates this subcase.

Subcase 3.4. $l_2 = 2^{n-1} - 4$. Let $\langle \mathbf {a}, \mathbf {b}, \mathbf {c}\rangle$ be a path of length 2 in $CQ^1_{n-1} - \{\mathbf {x}, \mathbf {y}\},$ such that $\{\mathbf {u}, \mathbf {v}\} \cap \{(\mathbf {a})^n, (\mathbf {c})^n\} = \emptyset$. By the inductive hypothesis, we can find two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $(\mathbf {a})^n$ with $l(R_1) = 2^{n-2} - 1$, and (ii) $R_2$ joins $(\mathbf {c})^n$ and $\mathbf {v}$ with $l(R_2) = 2^{n-2} - 1$. By Lemma 5, there exists a Hamiltonian path $S$ in $CQ^1_{n-1} - \{\mathbf {a}, \mathbf {b}, \mathbf {c}\}$ joining $\mathbf {x}$ and $\mathbf {y}$. Then, $P_1 = \langle \mathbf {u}, R_1, (\mathbf {a})^n, \mathbf {a}, \mathbf {b}, \mathbf {c}, (\mathbf {c})^n, R_2, \mathbf {v}\rangle$ and $P_2 = S$ are our required paths. The illustration of this subcase is shown in Fig. 4c.

Fig. 5

Case 5 in the proof of Theorem 1 (a dashed line or a straight line represents an edge)

Subcase 3.5. $n \le l_2 \le 2^{n-1} - 5$. By Lemma 9, we can find a Hamiltonian path $S$ of $CQ^1_{n-1},$ such that $S(1) = \mathbf {x}$ and $S(l_2+1) = \mathbf {y}$. Path $S$ can be written as $\langle \mathbf {x}, S_1, \mathbf {y}, \mathbf {a}, S_2, \mathbf {b}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b}$, where $\mathbf {a}$ is a neighbor of $\mathbf {y}$ on $S$. The following conditions are distinguished.

Condition 3.5.1. $| \{\mathbf {u}, \mathbf {v}\} \cap \{(\mathbf {a})^n, (\mathbf {b})^n\} | = 0$. By the inductive hypothesis, we obtain two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $(\mathbf {a})^n$ with $l(R_1) = 2^{n-2} - 1$, and (ii) $R_2$ joins $(\mathbf {b})^n$ and $\mathbf {v}$ with $l(R_2) = 2^{n-2} - 1$. Then, $P_1 = \langle \mathbf {u}, R_1, (\mathbf {a})^n, \mathbf {a}, S_2, \mathbf {b}, (\mathbf {b})^n, R_2, \mathbf {v}\rangle$ and $P_2 = S_1$ are our required paths. See Fig. 4d for illustration.

Condition 3.5.2. $| \{\mathbf {u}, \mathbf {v}\} \cap \{(\mathbf {a})^n, (\mathbf {b})^n\} | = 1$. Without loss of generality, we assume that $\mathbf {u} = (\mathbf {a})^n$ and $\mathbf {v} \ne (\mathbf {b})^n$. By Lemma 3, $CQ^0_{n-1} - \{\mathbf {u}\}$ has a Hamiltonian path $R$ joining $(\mathbf {b})^n$ and $\mathbf {v}$. We set $P_1 = \langle \mathbf {u}, \mathbf {a}, S_2, \mathbf {b}, (\mathbf {b})^n, R, \mathbf {v}\rangle$ and $P_2 = S_1$. Then, $P_1$ and $P_2$ are our required paths. See Fig. 4e for illustration.

Condition 3.5.3. $| \{\mathbf {u}, \mathbf {v}\} \cap \{(\mathbf {a})^n, (\mathbf {b})^n\} | = 2$. Without loss of generality, we assume that $\mathbf {u} = (\mathbf {a})^n$ and $\mathbf {v} = (\mathbf {b})^n$. We write $S_2$ as $\langle \mathbf {a}, S^1_2, \mathbf {p}, \mathbf {q}, S^2_2, \mathbf {b}\rangle$ for some vertices $\mathbf {p}$ and $\mathbf {q}$. Obviously, there exists a Hamiltonian path $R$ in $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {v}\}$ joining $(\mathbf {p})^n$ and $(\mathbf {q})^n$. Then, $P_1 = \langle \mathbf {u}, \mathbf {a}, S^1_2, \mathbf {p}, (\mathbf {p})^n, R, (\mathbf {q})^n, \mathbf {q}, S^2_2, \mathbf {b}, \mathbf {v}\rangle$ and $P_2 = S_1$ are the required paths. Figure 4f illustrates this condition.

Case 4. $\mathbf {u} \in V(CQ^0_{n-1})$ and $\{\mathbf {v}, \mathbf {x}, \mathbf {y}\} \subset V(CQ^1_{n-1})$. This case is similar to Case 2, in which $\mathbf {u}$ and $\mathbf {v}$ are in different subcubes whereas $\mathbf {x}$ and $\mathbf {y}$ are in the same one.

Case 5. $\{\mathbf {u}, \mathbf {v}, \mathbf {x}\} \subset V(CQ^0_{n-1})$ and $\mathbf {y} \in V(CQ^1_{n-1})$. Consider the following subcases.

Subcase 5.1. $2n - 1 \le l_2 \le 2^{n-1} - 1$. Let $\mathbf {p}$ be a vertex of $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {v}, \mathbf {x}\}$ with $(\mathbf {p})^n \ne \mathbf {y}$. By the inductive hypothesis, there exist two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $\mathbf {v}$ with $l(R_1) = 2^{n-1} - n - 1$, and (ii) $R_2$ joins $\mathbf {x}$ and $\mathbf {p}$ with $l(R_2) = n - 1$. We can write $R_1$ as $\langle \mathbf {u}, R^1_1, \mathbf {a}, \mathbf {b}, R^2_1, \mathbf {v}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b},$ such that $\mathbf {y} \not \in \{(\mathbf {a})^n, (\mathbf {b})^n\}$. Also by the inductive hypothesis, there exist two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $(\mathbf {b})^n$ with $l(S_1) = 2^{n-1} - l_2 + n - 2$, and (ii) $S_2$ joins $(\mathbf {p})^n$ and $\mathbf {y}$ with $l(S_2) = l_2 - n$. By setting $P_1 = \langle \mathbf {u}, R^1_1, \mathbf {a}, (\mathbf {a})^n, S_1, (\mathbf {b})^n, \mathbf {b}, R^2_1, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, R_2, \mathbf {p}, (\mathbf {p})^n, S_2, \mathbf {y}\rangle ,\, P_1$ and $P_2$ are the required paths. The illustration of this subcase is shown in Fig. 5a.

Subcase 5.2. $(\mathbf {x}, \mathbf {y}) \not \in E(CQ_n)$ and $n \le l_2 \le 2n - 2$. By Lemma 3, there exists a Hamiltonian path $R$ in $CQ^0 _{n-1} - \{\mathbf {x}\}$ joining $\mathbf {u}$ and $\mathbf {v}$. We can write $R$ as $\langle \mathbf {u}, R_1, \mathbf {a}, \mathbf {b}, R_2, \mathbf {v}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b},$ such that $\mathbf {y} \not \in \{(\mathbf {a})^n, (\mathbf {b})^n\}$. By the inductive hypothesis, there exist two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $(\mathbf {b})^n$ with $l(S_1) = 2^{n-1} - l_2 - 1$, and (ii) $S_2$ joins $(\mathbf {x})^n$ and $\mathbf {y}$ with $l(R_2) = l_2 - 1$. Then, $P_1 = \langle \mathbf {u}, R_1, \mathbf {a}, (\mathbf {a})^n, S_1, (\mathbf {b})^n, \mathbf {b}, R_2, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, (\mathbf {x})^n, S_2, \mathbf {y}\rangle$ are our required paths. See Fig. 5b for illustration.

Subcase 5.3. $(\mathbf {x}, \mathbf {y}) \in E(CQ_n)$ and $n + 1 \le l_2 \le 2n - 2$. Let $\mathbf {p}$ be a neighbor of $\mathbf {x}$ in $CQ^0_{n-1}$ with $\mathbf {p} \not \in \{\mathbf {u}, \mathbf {v}\}$. By Lemma 3, we have a Hamiltonian path $R$ of $CQ^0_{n-1} - \{\mathbf {x}, \mathbf {p}\}$ joining $\mathbf {u}$ and $\mathbf {v}$. $R$ can be written as $\langle \mathbf {u}, R_1, \mathbf {a}, \mathbf {b}, R_2, \mathbf {v}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b}$. By the inductive hypothesis, we have two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $(\mathbf {b})^n$ with $l(S_1) = 2^{n-1} - l_2$, and (ii) $S_2$ joins $(\mathbf {p})^n$ and $\mathbf {y}$ with $l(S_2) = l_2 - 2$. We set $P_1 = \langle \mathbf {u}, R_1, \mathbf {a}, (\mathbf {a})^n, S_1, (\mathbf {b})^n, \mathbf {b}, R_2, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, \mathbf {p}, (\mathbf {p})^n, S_2, \mathbf {y}\rangle$. Then, $P_1$ and $P_2$ are our required paths as shown in Fig. 5c.

Subcase 5.4. $(\mathbf {x}, \mathbf {y}) \in E(CQ_n)$ and $l_2 = n$. The following conditions should be considered.

Condition 5.4.1. $n = 6$. Let $R_1 = \langle \mathbf {x}, \mathbf {w}, \mathbf {p}\rangle = \langle \mathbf {x}, (\mathbf {x})^i, ((\mathbf {x})^i)^1\rangle$ be a path of $CQ^0_{n-1}$ and $S_1 = \langle (\mathbf {p})^n, \mathbf {q}, \mathbf {t}, \mathbf {y}\rangle = \langle (((\mathbf {y})^i)^1)^2, ((\mathbf {y})^i)^1, (\mathbf {y})^i, \mathbf {y}\rangle$ be a path of $CQ^1_{n-1}$ for some $i$, $i \in \{2, 4, 5\}$, such that $\{\mathbf {w}, \mathbf {p}\} \cap \{\mathbf {u}, \mathbf {v}\} = \emptyset$. By Lemma 5, there exists a Hamiltonian path $R_2$ in $CQ^0_{n-1} - V(R_1)$ joining $\mathbf {u}$ and $\mathbf {v}$. We can write $R_2$ as $\langle \mathbf {u}, R^1_2, \mathbf {a}, \mathbf {b}, R^2_2, \mathbf {v}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b}$ with $\{(\mathbf {a})^n, (\mathbf {b})^n\} \cap \{\mathbf {q}, \mathbf {t}\} = \emptyset$. By Lemma 6, there exists a Hamiltonian path $S_2$ in $CQ^1_{n-1} - V(S_1)$ joining $(\mathbf {a})^n$ and $(\mathbf {b})^n$. Then, $P_1 = \langle \mathbf {u}, R^1_2, \mathbf {a}, (\mathbf {a})^n, S_2, (\mathbf {b})^n, \mathbf {b}, R^2_2, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, R_1, \mathbf {p}, (\mathbf {p})^n, S_1, \mathbf {y}\rangle$ are the required paths. See Fig. 5d for illustration.

Condition 5.4.2. $n \ge 7$. Let $R_1 = \langle \mathbf {x}, \mathbf {z}, \mathbf {w}, \mathbf {p}\rangle = \langle \mathbf {x}, (\mathbf {x})^{i-1}, ((\mathbf {x})^i)^{i-1}, (\mathbf {x})^i\rangle$ be a path of $CQ^0_{n-1}$ for some $i,\, i \in \{2, 4, 6\}$, such that $\{\mathbf {z}, \mathbf {w}, \mathbf {p}\} \cap \{\mathbf {u}, \mathbf {v}\} = \emptyset$. Then, Lemmas 1 and 9 ensure that $CQ^1_{n-1}$ has a path $S_1$ of length $n - 4$ joining $(\mathbf {p})^n$ and $\mathbf {y}$. By Lemma 6, there exists a Hamiltonian path $R_2$ in $CQ^0_{n-1} - V(R_1)$ joining $\mathbf {u}$ and $\mathbf {v}$. We write $R_2$ as $\langle \mathbf {u}, R^1_2, \mathbf {a}, \mathbf {b}, R^2_2, \mathbf {v}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b}$ with $\{(\mathbf {a})^n, (\mathbf {b})^n\} \cap V(S_1) = \emptyset$. By Lemma 7, we have a Hamiltonian path $S_2$ of $CQ^1_{n-1} - V(S_1)$ joining $(\mathbf {a})^n$ and $(\mathbf {b})^n$. Then, $P_1 = \langle \mathbf {u}, R^1_2, \mathbf {a}, (\mathbf {a})^n, S_2, (\mathbf {b})^n, \mathbf {b}, R^2_2, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, R_1, \mathbf {p}, (\mathbf {p})^n, S_1, \mathbf {y}\rangle$ are the required paths. See Fig. 5e for illustration.

Case 6. $\{\mathbf {u}, \mathbf {x}\} \subset V(CQ^0_{n-1})$ and $\{\mathbf {v}, \mathbf {y}\} \subset V(CQ^1_{n-1})$. Four subcases should be considered.

Subcase 6.1. $2n - 1 \le l_2 \le 2^{n-1} - 1$. Let $\mathbf {a}$ and $\mathbf {p}$ be two vertices of $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {x}\}$ with $\{(\mathbf {a})^n, (\mathbf {p})^n\} \cap \{\mathbf {v}, \mathbf {y}\} = \emptyset$. By the inductive hypothesis, there exist two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $\mathbf {a}$ with $l(R_1) = 2^{n-1} - n - 1$, and (ii) $R_2$ joins $\mathbf {x}$ and $\mathbf {p}$ with $l(R_2) = n - 1$. Also by the inductive hypothesis, there exist two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $\mathbf {v}$ with $l(S_1) = 2^{n-1} - l_2 + n - 2$, and (ii) $S_2$ joins $(\mathbf {p})^n$ and $\mathbf {y}$ with $l(S_2) = l_2 - n$. We set $P_1 = \langle \mathbf {u}, R_1, \mathbf {a}, (\mathbf {a})^n, S_1, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, R_2, \mathbf {p}, (\mathbf {p})^n, S_2, \mathbf {y}\rangle$. Obviously, $P_1$ and $P_2$ are the required paths as shown in Fig. 6a.

Fig. 6

Case 6 in the proof of Theorem 1 (a dashed line or a straight line represents an edge)

Subcase 6.2. $(\mathbf {x}, \mathbf {y}) \not \in E(CQ_n)$ and $\{(\mathbf {x})^n,(\mathbf {y})^n\} \ne \{\mathbf {u},\mathbf {v}\}$ and $n \le l_2 \le 2n - 2$. Without loss of generality, assume $(\mathbf {y})^n \ne \mathbf {u}$. Let $\mathbf {a}$ be a vertex of $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {x}, (\mathbf {y})^n\}$ with $(\mathbf {a})^n \ne \mathbf {v}$. By the inductive hypothesis, we have two vertex-disjoint paths $R_1$ and $R_2$ in $CQ^0_{n-1},$ such that (i) $R_1$ joins $\mathbf {u}$ and $\mathbf {a}$ with $l(R_1) = 2^{n-1} - l_2 - 1$, and (ii) $R_2$ joins $\mathbf {x}$ and $(\mathbf {y})^n$ with $l(R_2) = l_2 - 1$. Because we have a Hamiltonian path $S$ of $CQ^1_{n-1} - \{\mathbf {y}\}$ joining $(\mathbf {a})^n$ and $\mathbf {v}$, we can set $P_1 = \langle \mathbf {u}, R_1, \mathbf {a}, (\mathbf {a})^n, S, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, R_2, (\mathbf {y})^n, \mathbf {y}\rangle$ to form our required paths. See Fig. 6b for illustration.

Subcase 6.3. $(\mathbf {x}, \mathbf {y}) \not \in E(CQ_n)$ and $\{(\mathbf {x})^n,(\mathbf {y})^n\} = \{\mathbf {u},\mathbf {v}\}$ and $n \le l_2 \le 2n - 2$. Let $\mathbf {p}$ be a neighbor of $\mathbf {x}$ in $CQ^0_{n-1}$ with $\mathbf {p} \ne \mathbf {u}$. The following conditions are distinguished.

Condition 6.3.1. $n + 1 \le l_2 \le 2n - 2$. Let $\mathbf {a}$ be any vertex of $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {x}, \mathbf {p}\}$. By Lemma 3, we have a Hamiltonian path $R$ of $CQ^0_{n-1} - \{\mathbf {x}, \mathbf {p}\}$ joining $\mathbf {u}$ and $\mathbf {a}$. By the inductive hypothesis, there exist two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $\mathbf {v}$ with $l(S_1) = 2^{n-1} - l_2$, and (ii) $S_2$ joins $(\mathbf {p})^n$ and $\mathbf {y}$ with $l(S_2) = l_2 - 2$. By setting $P_1 = \langle \mathbf {u}, R, \mathbf {a}, (\mathbf {a})^n, S_1, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, \mathbf {p}, (\mathbf {p})^n, S_2, \mathbf {y}\rangle$, $P_1$ and $P_2$ are our required paths as shown in Fig. 6c.

Condition 6.3.2. $l_2 = n$. By Lemma 10, we have a path $S$ of length $n - 2$ in $CQ^1_{n-1} - \{\mathbf {v}\}$ joining $(\mathbf {p})^n$ and $\mathbf {y}$. We write $S$ as $\langle (\mathbf {p})^n, S', \mathbf {q}, \mathbf {y}\rangle$. By Lemma 7, there exists a Hamiltonian path $T$ in $CQ^1_{n-1} - V(S')$ joining $\mathbf {y}$ and $\mathbf {v}$, and $T$ can be written as $\langle \mathbf {y}, \mathbf {z}, T', \mathbf {v}\rangle$. In $CQ^0_{n-1} - \{\mathbf {x}, \mathbf {p}\}$, we have a Hamiltonian path $R$ joining $\mathbf {u}$ and $(\mathbf {z})^n$. Then, $P_1 = \langle \mathbf {u}, R, (\mathbf {z})^n, \mathbf {z}, T', \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, \mathbf {p}, (\mathbf {p})^n, S', \mathbf {q}, \mathbf {y}\rangle$ are our required paths. See Fig. 6d for illustration.

Subcase 6.4. $(\mathbf {x}, \mathbf {y}) \in E(CQ_n)$ and $n + 1 \le l_2 \le 2n - 2$. Let $\mathbf {p}$ be a neighbor of $\mathbf {x}$ in $CQ^0_{n-1}$ with $\mathbf {p} \ne \mathbf {u}$ and $(\mathbf {p})^n \ne \mathbf {v}$. Moreover, let $\mathbf {a}$ be a vertex of $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {x}, \mathbf {p}\}$ with $(\mathbf {a})^n \ne \mathbf {v}$. By Lemma 3, there exists a Hamiltonian path $R$ in $CQ^0_{n-1} - \{\mathbf {x}, \mathbf {p}\}$ joining $\mathbf {u}$ and $\mathbf {a}$. By the inductive hypothesis, we have two vertex-disjoint paths $S_1$ and $S_2$ in $CQ^1_{n-1},$ such that (i) $S_1$ joins $(\mathbf {a})^n$ and $\mathbf {v}$ with $l(S_1) = 2^{n-1} - l_2$, and (ii) $S_2$ joins $(\mathbf {p})^n$ and $\mathbf {y}$ with $l(S_2) = l_2 - 2$. Then, $P_1 = \langle \mathbf {u}, R, \mathbf {a}, (\mathbf {a})^n, S_1, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, \mathbf {p}, (\mathbf {p})^n, S_2, \mathbf {y}\rangle$ are the required paths.

Subcase 6.5. $(\mathbf {x}, \mathbf {y}) \in E(CQ_n)$ and $l_2 = n$. Let $\mathbf {p}$ be a neighbor of $\mathbf {x}$ in $CQ^0_{n-1},$ such that $\mathbf {p} \ne \mathbf {u}$ and $(\mathbf {p})^n \ne \mathbf {v}$. By Lemma 10, there exists a path $S$ of length $n - 2$ in $CQ^1_{n-1} - \{\mathbf {v}\}$ joining $(\mathbf {p})^n$ and $\mathbf {y}$. We write $S$ as $\langle (\mathbf {p})^n, \mathbf {q}, S', \mathbf {y}\rangle$. By Lemma 7, we have a Hamiltonian path $T$ of $CQ^1_{n-1} - V(S')$ joining $(\mathbf {p})^n$ and $\mathbf {v}$, and $T$ can be written as $\langle (\mathbf {p})^n, \mathbf {z}, T', \mathbf {v}\rangle$. Then, consider the following two conditions.

Condition 6.5.1. $(\mathbf {z})^n \ne \mathbf {u}$. Because there exists a Hamiltonian path $R$ in $CQ^0_{n-1} - \{\mathbf {x}, \mathbf {p}\}$ joining $\mathbf {u}$ and $(\mathbf {z})^n$, we can set $P_1 = \langle \mathbf {u}, R, (\mathbf {z})^n, \mathbf {z}, T', \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, \mathbf {p}, (\mathbf {p})^n, \mathbf {q}, S', \mathbf {y}\rangle$. Then, $P_1$ and $P_2$ are the required paths. See Fig. 6e for illustration.

Condition 6.5.2. $(\mathbf {z})^n = \mathbf {u}$. For convenience, we rewrite $T'$ as $\langle \mathbf {z}, T_1, \mathbf {a}, \mathbf {b}, T_2, \mathbf {v}\rangle$ for some vertices $\mathbf {a}$ and $\mathbf {b}$. By Lemma 5, there exists a Hamiltonian path $R$ in $CQ^0_{n-1} - \{\mathbf {u}, \mathbf {x}, \mathbf {p}\}$ joining $(\mathbf {a})^n$ and $(\mathbf {b})^n$. Then, $P_1 = \langle \mathbf {u}, \mathbf {z}, T_1, \mathbf {a}, (\mathbf {a})^n, R, (\mathbf {b})^n, \mathbf {b}, T_2, \mathbf {v}\rangle$ and $P_2 = \langle \mathbf {x}, \mathbf {p}, (\mathbf {p})^n, \mathbf {q}, S', \mathbf {y}\rangle$ are our required paths. See Fig. 6f for illustration.

The above argument of all cases completes the proof. $\square$

4 Concluding remarks

The crossed cube architecture is a popular variant of the hypercube network owing to its useful topological properties. In particular, a $k$-DPC can be found in the crossed cube [37, 38]. Previous work [33] addressed a method for finding a $2$-DPC of a crossed cube whose vertex-disjoint paths have the same length. In this paper, we studied the 2-DPC panconnectedness of the crossed cube whose vertex-disjoint paths have diverse lengths. The brute force search result of running a computer program on $CQ_5$ indicated that there is no path of length four in $CQ_5 - \{\mathbf {u}, \mathbf {v}\}$ joining $\mathbf {x}$ and $\mathbf {y}$, if $\mathbf {u},\, \mathbf {v},\, \mathbf {x}$, and $\mathbf {y}$ form a $C_4$ with conditions such as (i) $\mathbf {v} = (\mathbf {u})^2,\, \mathbf {x} = (\mathbf {u})^1$, and $\mathbf {y} = ((\mathbf {u})^1)^2$, and (ii) $\mathbf {v} = ((\mathbf {u})^1)^2,\, \mathbf {x} = (\mathbf {u})^1$, and $\mathbf {y} = (\mathbf {u})^2$. Furthermore, there is no path of length three in $CQ_5 - \{\mathbf {u}, \mathbf {v}\}$ joining $\mathbf {x}$ and $\mathbf {y}$, if $\mathbf {u},\, \mathbf {v},\, \mathbf {x}$, and $\mathbf {y}$ form a $C_4$ with conditions such as $\mathbf {v} = (\mathbf {u})^1,\, \mathbf {x} = (\mathbf {u})^2$, and $\mathbf {y} = ((\mathbf {u})^2)^1$. Consequently, we showed that the crossed cube $CQ_n$ is $2$-DPC $n$-panconnected for $n \ge 5$.