# Two kinds of generalized connectivity of dual cubes

Shu-Li Zhao1, Rong-Xia Hao1***Corresponding author.
Email:17118434@bjtu.edu.cn(S.-L. Zhao<EMAIL_ADDRESS>(R.-X. Hao),
echeng@oakland.edu(E. Cheng), Eddie Cheng2
1Department of Mathematics, Beijing Jiaotong University,
Beijing 100044, P.R. China
2Department of Mathematics and Statistics, Oakland University,
Rochester, MI 48309, USA

Let $S\subseteq V(G)$ and $\kappa_{G}(S)$ denote the maximum number $k$ of
edge-disjoint trees $T_{1},T_{2},\cdots,\\\ T_{k}$ in $G$ such that
$V(T_{i})\bigcap V(T_{j})=S$ for any $i,j\in\\{1,2,\cdots,k\\}$ and $i\neq j$.
For an integer $r$ with $2\leq r\leq n$, the generalized $r$-connectivity of a
graph $G$ is defined as $\kappa_{r}(G)=min\\{\kappa_{G}(S)|S\subseteq V(G)$
and $|S|=r\\}$. The $r$-component connectivity $c\kappa_{r}(G)$ of a non-
complete graph $G$ is the minimum number of vertices whose deletion results in
a graph with at least $r$ components. These two parameters are both
generalizations of traditional connectivity. Except hypercubes and complete
bipartite graphs, almost all known $\kappa_{r}(G)$ are about $r=3$. In this
paper, we focus on $\kappa_{4}(D_{n})$ of dual cube $D_{n}$. We first show
that $\kappa_{4}(D_{n})=n-1$ for $n\geq 4$. As a corollary, we obtain
$\kappa_{3}(D_{n})=n-1$ for $n\geq 4$. Furthermore, we show that
$c\kappa_{r+1}(D_{n})=rn-\frac{r(r+1)}{2}+1$ for $n\geq 2$ and $1\leq r\leq
n-1$.

Keywords: Generalized connectivity; Component connectivity; Fault-tolerance;
Dual cube.

##  1 Introduction

For an interconnection network, one major concern is the fault tolerance. An
interconnection network is usually modelled by a connected graph $G=(V,E)$,
where nodes represent processors and edges represent communication links
between processors. The connectivity is one of the important parameters to
evaluate the reliability and fault tolerance of a network. The connectivity
$\kappa(G)$ of a graph $G$ is defined as the minimum number of vertices whose
deletion results in a disconnected graph. Whitney [20] provides another
definition of connectivity. For any subset $S=\\{u,v\\}\subseteq V(G)$, let
$\kappa_{G}(S)$ denote the maximum number of internally disjoint paths between
$u$ and $v$ in $G$. Then $\kappa(G)=min\\{\kappa_{G}(S)|S\subseteq V(G)$ and
$|S|=2\\}$. As generalizations of the traditional connectivity, the
generalized $k$-connectivity and the $r$-component connectivity were
introduced by Chartrand $et$ $al.$ [3] in $1984$.

Let $G$ be a non-complete graph. A $r$-component cut of $G$ is a set of
vertices whose deletion results in a graph with at least $r$ components. The
$r$-component connectivity $c\kappa_{r}(G)$ of a graph $G$ is the size of the
smallest $r$-component cut of $G$. By the definition of $c\kappa_{r}(G)$, it
can be seen that $c\kappa_{r+1}(G)\geq c\kappa_{r}(G)$ for every positive
integer $r$. The $r$-component connectivity is an extension of the usual
connectivity $c\kappa_{2}(G)$. In [5], Hsu $et$ $al.$ determined the
$r$-component connectivity of the hypercube $Q_{n}$ for $r=2,3,\cdots,n+1$. In
[25], Zhao $et$ $al.$ determine the $r$-component connectivity of the
hypercube $Q_{n}$ for $r=n+2,n+3,\cdots,2n-4$.

Let $S\subseteq V(G)$ and $\kappa_{G}(S)$ denote the maximum number $k$ of
edge-disjoint trees $T_{1},T_{2},\cdots,\\\ T_{k}$ in $G$ such that
$V(T_{i})\bigcap V(T_{j})=S$ for any $i,j\in\\{1,2,\cdots,k\\}$ and $i\neq j$.
For an integer $r$ with $2\leq r\leq n$, the generalized $r$-connectivity of a
graph $G$ is defined as $\kappa_{r}(G)=min\\{\kappa_{G}(S)|S\subseteq V(G)$
and $|S|=r\\}$. It is a parameter that can measure the reliability of a
network $G$ to connect any $k$ vertices in $G$. If $\kappa_{r}(G)=m$, then
there are $m$ internally disjoint trees in $G$ and each of them connecting the
vertices of $S$, where $|S|=r$ be any $S$ of $V(G)$. The generalized
$2$-connectivity is exactly the traditional connectivity. In [10], Li $et$
$al.$ derived that it is NP-complete for a general graph $G$ to decide whether
there are $k$ internally disjoint trees connecting $S$, where $k$ is a fixed
integer and $S\subseteq V(G).$ There are some results [8, 12] about the upper
and lower bounds of the generalized connectivity. In addition, there are some
results of the generalized $k$-connectivity for some classes of graphs and
most of them are about $k=3$. For example, Chartrand et al. [4] studied the
generalized connectivity of complete graphs; Li $et$ $al.$ [6] first studied
the generalized $3$-connectivity of Cartesian product graphs, then Li $et$
$al.$ [11] studied the generalized $3$-connectivity of graph products; Li $et$
$al.$ [13] studied the generalized connectivity of the complete bipartite
graphs and Lin $et$ $al.$ [14] studied the generalized $4$-connectivity of
hypercubes. As the Cayley graph has some attractive properties to design
interconnection networks, Li $et$ $al.$ [9] studied the generalized
$3$-connectivity of star graphs and bubble-sort graphs and Li $et$ $al.$ [7]
studied the generalized $3$-connectivity of the Cayley graph generated by
trees and cycles. Except hypercubes and complete bipartite graphs, almost all
known exact value of the generalized $k$-connectivity are about $k=3$.

In this paper, we first show that $\kappa_{4}(D_{n})=\kappa_{3}(D_{n})=n-1$
for $n\geq 4$, then we show that $c\kappa_{r+1}(D_{n})=rn-\frac{r(r+1)}{2}+1$
for $n\geq 2$ and $1\leq r\leq n-1$.

The paper is organized as follows. In section 2, some notations and
definitions are given. In section 3, the generalized $4$-connectivity and the
generalized $3$-connectivity of dual cubes are determined. In section 4, the
$r$-component connectivity of the dual cube for $n\geq 2$ and $2\leq r\leq
n-1$ is determined. In section 5, the paper is concluded.

##  2 Preliminary

Let $G=(V,E)$ be a simple, undirected graph. Let $|V(G)|$ and $|E(G)|$ denote
the order and size of graph $G$, respectively. Let $V^{\prime}\subseteq V(G)$,
then $G[V^{\prime}]$ is the subgraph of $G$ whose vertex set is $V^{\prime}$
and whose edge set consists of all edges of $G$ which have both ends in
$V^{\prime}$. For a vertex $v\in V(G)$, the set of neighbours of a vertex $v$
in a graph $G$ is denoted by $N_{G}(v)$. For a vertex set $U\subseteq V(G)$,
the neighborhood of $U$ in $G$ is defined as $N_{G}(U)=\bigcup\limits_{v\in
U}N_{G}(v)-U$. Let $d_{G}(v)$ denote the number of edges incident with $v$ and
$\delta(G)$ denote the minimum degree of the graph $G$. A graph is said to be
$k$-regular if for any vertex $v$ of $G$, $d_{G}(v)=k$. Two $xy$\- paths $P$
and $Q$ in $G$ are internally disjoint if they have no common internal
vertices, that is $V(P)\bigcap V(Q)=\\{x,y\\}$. Let $Y\subseteq V(G)$ and
$X\subset V(G)\setminus Y$, the $(X,Y)$-paths is a family of internally
disjoint paths starting at a vertex $x\in X$, ending at a vertex $y\in Y$ and
whose internal vertices belong neither to $X$ nor $Y$. If $X=\\{x\\}$, then
the $(X,Y)$-paths is a family of internal disjoint paths whose starting vertex
is $x$ and the terminal vertices are distinct in $Y$, which is referred to as
a $k$-fan from $x$ to $Y$. For terminologies and notations not defined here we
follow [2].

The hypercube is one of the most fundamental interconnection network. An
$n$-dimensi
onal hypercube is an undirected graph $Q_{n}=(V,E)$ with $|V|=2^{n}$ and
$|E|=n2^{n-1}.$ Each vertex can be represented by an $n$-bit binary string.
There is an edge between two vertices whenever their binary string
representation differs in only one bit position. The dual-cube was introduced
by Li and Peng in [14]. As an invariant of the hypercube, it not only keeps
numerous desirable properties of the hypercube, but also reduces the
interconnection complexity. The $n$-dimensional dual cube, denoted by $D_{n}$,
has $2^{2n-1}$ vertices, each labeled by a $(2n-1)$-bit binary string
$u_{1}u_{2}\cdots u_{2n-1}$, and $u_{i}\in\\{0,1\\}$ for $i=1,2\cdots,2n-1.$
Two vertices $u=u_{1}u_{2}\cdots u_{2n-1}$ and $v=v_{1}v_{2}\cdots v_{2n-1}$
are adjacent if and only if the following conditions are satisfied:

$(1)$ $u$ and $v$ differ in exactly one bit position $i$.

$(2)$ If $1\leq i\leq n-1$, then $u_{2n-1}=v_{2n-1}=0$.

$(3)$ If $n\leq i\leq 2n-2$, then $u_{2n-1}=v_{2n-1}=1$.

By the definition of the $n$-dimensional dual cube, we can see that the set of
vertices with fixed bits in positions $n,\cdots,2n-2$ and last bit $0$ form an
$(n-1)$-dimensional hypercube, which is called a cluster of class $0$. And the
set of vertices with fixed bits in positions $1,\cdots,n-1$ and last bit $1$
also form an $(n-1)$-dimensional hypercube, which is called a cluster of class
$1$. Edges connecting two vertices in different clusters of different class
are called cross edges. Let $v$ be a vertex of cluster $0(1)$, then we call
the neighbour of the vertex $v$ in cluster $1(0)$ the outside neighbour of $v$
in $D_{n}$. The $n$-dimensional dual cube has $2^{n-1}$ clusters of class $0$
and $2^{n-1}$ clusters of class $1$. For convenience, we denote the clusters
of class $0$ by $D_{01},D_{02},\cdots$ and $D_{02^{n-1}}$, respectively. And
we denote the clusters of class $1$ by $D_{11},D_{12},\cdots$ and
$D_{12^{n-1}}$, respectively. The $3$-dimensional dual cube is shown as figure
$1$.

Figure 1: The $3-$dimensional dual cube

The $n$-dimensional dual cube $D_{n}$ is an $n$-regular graph. It consists of
$2^{n}$ clusters, half of them are class $0$, and the other half of them is
class $1$. There are many research results about dual cubes, one can refer [1,
23, 24] etc. for the detail.

##  3 The generalized $4$-connectivity of dual cubes

In this section, we will study the generalized $4$-connectivity of dual cubes.
The following results are useful to the main result.

######  Lemma 1.

Let $D_{n}$ be an $n$-dimensional dual cube for $n\geq 2$. Then the following
results hold.

  1. (1)

Any two different vertices in the same cluster of $D_{n}$ have different
outside neighbours and they belong to different clusters of $D_{n}$.

  2. (2)

There is exactly one cross edge between two clusters of different class in
$D_{n}$.

Proof. (1) Let $D_{01},D_{02},\cdots,D_{02^{n-1}}$ be the clusters of class
$0$ and $D_{11},D_{12},\cdots,D_{12^{n-1}}$ be the clusters of class $1$ of
$D_{n}$. Without loss of generality, let $u,v\in V(D_{01})$ and $u\neq v$. Let
$u=u_{1}u_{2}\cdots u_{n-1}u_{n}\cdots u_{2n-2}0$ and $v=v_{1}v_{2}\cdots
v_{n-1}v_{n}\cdots v_{2n-2}0$. As $u\neq v$, then $u_{1}u_{2}\cdots u_{n-1}$
and $v_{1}v_{2}\cdots v_{n-1}$ have at least one different digit. The outside
neighbour $u^{\prime}$ of $u$ is $u^{\prime}=u_{1}u_{2}\cdots
u_{n-1}u_{n}\cdots u_{2n-2}1$ and the outside neighbour $v^{\prime}$ of $v$ is
$v^{\prime}=v_{1}v_{2}\cdots v_{n-1}v_{n}\cdots v_{2n-2}1$. If $u^{\prime}$
and $v^{\prime}$ belong to the same cluster, then $u_{1}u_{2}\cdots
u_{n-1}=v_{1}v_{2}\cdots v_{n-1}$ by the definition of $D_{n}$, which is a
contradiction.

(2) By $(1)$, the result holds easily. ∎

######  Lemma 2.

([2]) $\kappa(Q_{n})=n$ for $n\geq 2$.

######  Theorem 1.

([14]) The generalized $4$-connectivity of hypercube $Q_{n}$ is $n-1$, where
$n\geq 2$.

######  Lemma 3.

([14]) Let $G$ be an $r$-regular graph. If $\kappa_{k}(G)=r-1$, then
$\kappa_{k-1}(G)=r-1$, where $k\geq 4$.

######  Lemma 4.

([12]) If there are two adjacent vertices of degree $\delta(G)$, then
$\kappa_{k}(G)\leq\delta-1$ for $3\leq k\leq|V(G)|$.

######  Lemma 5.

([2]) Let $G=(V,E)$ be a $k$-connected graph, let $x$ be a vertex of $G$, and
let $Y\subseteq V\setminus\\{x\\}$ be a set of at least $k$ vertices of $G$.
Then there exists a $k$-fan in $G$ from $x$ to $Y$. That is, there exists a
family of $k$ internally vertex-disjoint $(x,Y)$-paths whose terminal vertices
are distinct in $Y$.

######  Theorem 2.

Let
$H=D_{n}[(\bigcup_{j=1}^{k}V(D_{0i_{j}}))\bigcup(\bigcup_{i=1}^{l}V(D_{1j_{i}}))]$,
where $k\geq 1,l\geq 1,$ $D_{0i_{j}}$ is a cluster of class $0$ of $D_{n}$ and
$D_{1j_{i}}$ is a cluster of class $1$ of $D_{n}$. Then $H$ is connected for
$n\geq 3$.

Proof. Without loss of generality, let
$H=D_{n}[(\bigcup_{j=1}^{k}V(D_{0j}))\bigcup(\bigcup_{i=1}^{l}V(D_{1i}))]$,
where $k\geq 1,l\geq 1,$ $D_{0j}$ is a cluster of class $0$ of $D_{n}$ and
$D_{1i}$ is a cluster of class $1$ of $D_{n}$. To prove the result, we just
need to show for any two distinct vertices $x$ and $y$ of $H$, there is a path
between $x$ and $y$ in $H$.

Case $1$. $x$ and $y$ belong to the same cluster.

Without loss of generality, let $x,y\in V(D_{01})$. As $D_{01}$ is connected.
Then there is a path $P$ between $x$ and $y$ in $D_{01}$. As $D_{01}$ is a
subgraph of $H$, then $P$ is a path between $x$ and $y$ in $H$.

Case $2$. $x$ and $y$ belong to two clusters of the same class.

Without loss of generality, let $x\in V(D_{01})$ and $y\in V(D_{02})$. By
Lemma 1(1), there is a vertex $u$ of $D_{01}$ such that $u^{1}$, the outside
neighbour of $u$, belongs to $D_{11}$. Similarly, there is a vertex $v$ of
$D_{02}$ such that $v^{1}$, the outside neighbour of $v$, belongs to $D_{11}$.
As $D_{01},D_{02}$ and $D_{11}$ are connected. Then there is a path $P$
between $x$ and $u$ in $D_{01}$, a path $Q$ between $u^{1}$ and $v^{1}$ in
$D_{11}$ and a path $R$ between $y$ and $v$ in $D_{02}$. If $u=x$, then the
path $P$ is the single vertex $x$ and if $v=y$, then the path $R$ is the
single vertex $y$. Let $\widehat{P}=xPuu^{1}Qv^{1}vRy$, then it is a path
between $x$ and $y$ in $H$.

Case $3$. $x$ and $y$ belong to two clusters of different class.

Without loss of generality, let $x\in V(D_{01})$ and $y\in V(D_{11})$. By
Lemma 1(1), there is a vertex $u$ of $D_{01}$ such that $u^{1}$, the outside
neighbour of $u$, belongs to $D_{11}$. As $D_{01}$ and $D_{11}$ are connected.
Then there is a path $P$ between $x$ and $u$ in $D_{01}$ and a path $Q$
between $u^{1}$ and $y$ in $D_{11}$. If $u=x$, then the path $P$ is the single
vertex $x$ and if $u^{1}=y$, then the path $Q$ is the single vertex $y$. Let
$\widehat{P}=xPuu^{1}Qy$, then it is a path between $x$ and $y$ in $H$. ∎

To prove the generalized $4$-connectivity of dual cubes, the following results
are useful.

######  Theorem 3.

Let $D_{n}$ be an $n$-dimensional dual cube and $S=\\{x,y,z,w\\}$, where
$x,y,z$ and $w$ are any four distinct vertices of $D_{n}$ for $n\geq 4$. If
the vertices in $S$ belong to two clusters of $D_{n}$, then there are $n-1$
internally disjoint trees connecting $S$ in $D_{n}$.

Proof. Let $D_{01},D_{02},\cdots,D_{02^{n-1}}$ be the clusters of class $0$
and $D_{11},D_{12},\cdots$ and $D_{12^{n-1}}$ be the clusters of class $1$ of
$D_{n}$. Let $S=\\{x,y,z,w\\}$, where $x,y,z$ and $w$ are any four distinct
vertices of $D_{n}$ for $n\geq 4$. Let the vertices in $S$ belong to two
clusters of $D_{n}$. By the symmetry of $D_{n}$, the following cases are
considered.

Case $1$. $|S\bigcap V(D_{0i})|=3$ and $|S\bigcap V(D_{0j})|=1$ for distinct
$i,j\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=3$ and $|S\bigcap
V(D_{02})|=1$. Let $\\{x,y,z\\}\subseteq V(D_{01})$ and $w\in V(D_{02})$. See
Figure $2$. As $x\neq y$, without loss of generality, we may assume that the
$(n-1)$-th digit of $x$ and $y$ are different. Hence, we may assume that
$x=x_{1}x_{2}\cdots x_{n-2}0H0$ and $y=y_{1}y_{2}\cdots y_{n-2}1H0$, where
$H=x_{n}x_{n+1}\cdots x_{2n-2}$. Assume the $(n-1)$-th digit of $z$ is $0$ and
we divide $D_{01}$ along the $(n-1)$th dimension into two copies of $Q_{n-2}$,
denoted by $Q^{n-1}[0]$ and $Q^{n-1}[1]$, respectively. Then $x,z\in
V(Q^{n-1}[0])$ and $y\in V(Q^{n-1}[1])$. By Lemma 2, $\kappa(Q_{n-2})=n-2$.
Then there are $n-2$ internally disjoint paths $P_{1},P_{2},\cdots,P_{n-2}$
between $x$ and $z$ in $Q^{n-1}[0]$. Let $x_{i}\in V(P_{i})$ such that
$y_{i}\in V(Q^{n-1}[1])$ and $y_{i}\neq y$, where $y_{i}$ is the neighbour of
$x_{i}$ in $Q^{n-1}[1]$. This can be done as any two different vertices in
$Q^{n-1}[0]$ have different neighbours in $Q^{n-1}[1]$ and $P_{i}$s are
internally disjoint for $1\leq i\leq n-2$. Let
$Y=\\{y_{1},y_{2},\ldots,y_{n-2}\\}$. By Lemma 2, $\kappa(Q^{n-1}[1])=n-2$. By
Lemma 5, there are $n-2$ internally disjoint paths
$P_{1}^{\prime},P_{2}^{\prime},\cdots,P_{n-2}^{\prime}$ from $y$ to $Y$. Let
$\widehat{T}_{i}=P_{i}\bigcup x_{i}y_{i}\bigcup P_{i}^{\prime}$ for each
$i\in\\{1,2,\cdots,n-2\\}$, then $n-2$ internally disjoint trees
$\widehat{T}_{i}$s for $1\leq i\leq n-2$ that connecting $x,y$ and $z$ are
obtained in $D_{01}$.

Figure 2: The illustration of Case $1$

Let $y_{i}^{1}$ be the outside neighbour of $y_{i}$ in $D_{n}$ for each
$i\in\\{1,2,\cdots,n-2\\}$. Without loss of generality, let $y_{i}^{1}\in
V(D_{1i})$ for $1\leq i\leq n-2$. Then choose $n-1$ vertices
$w_{1},w_{2},\cdots,w_{n-1}$ from $D_{02}$ such that $w_{i}^{1}$, the outside
neighbour of $w_{i}$ in $D_{n}$, belongs to $D_{1i}$ for each
$i\in\\{1,2,\cdots,n-1\\}$. For convenience, let
$W=\\{w_{1},w_{2},\cdots,w_{n-1}\\}$. By Lemma 2, $\kappa(D_{02})=n-1$ as
$D_{02}$ is a copy of $Q_{n-1}$. By Lemma 5, there are $n-1$ internally
disjoint paths $Q_{1},Q_{2},\cdots,Q_{n-1}$ from $w$ to $W$ and let the
terminal vertex of $Q_{i}$ is $w_{i}$ for each $i\in\\{1,2,\cdots,n-2\\}$. As
$D_{1i}$ is connected for $1\leq i\leq n-2$, then there is a path $R_{i}$
between $y_{i}^{1}$ and $w_{i}^{1}$ in $D_{1i}$ for each
$i\in\\{1,2,\cdots,n-2\\}$.

Let $T_{i}=\widehat{T}_{i}\bigcup Q_{i}\bigcup R_{i}\bigcup
y_{i}y_{i}^{1}\bigcup w_{i}w_{i}^{1}$ for each $i\in\\{1,2,\cdots,n-2\\}$.
Then $n-2$ internally disjoint trees $T_{i}$s for $1\leq i\leq n-2$ that
connecting $x,y,z$ and $w$ are obtained. Let $x^{1},y^{1}$ and $z^{1}$ be the
outside neighbours of $x,y$ and $z$ in $D_{n}$, respectively. By Lemma 1(2),
$\\{x^{1},y^{1},z^{1},w_{n-1}^{1}\\}\subset
V(D_{n}-\bigcup_{i=1}^{2}D_{0i}-\bigcup_{i=1}^{n-2}D_{1i})$. As $2^{n-1}>n-2$
for $n\geq 4$. By Theorem 2,
$D_{n}-\bigcup_{i=1}^{2}D_{0i}-\bigcup_{i=1}^{n-2}D_{1i}$ is connected. Then
there is a tree $\widetilde{T}_{n-1}$ connecting $x^{1},y^{1},z^{1}$ and
$w_{n-1}^{1}$ in $D_{n}-\bigcup_{i=1}^{2}D_{0i}-\bigcup_{i=1}^{n-2}D_{1i}$.
Let $T_{n-1}=\widetilde{T}_{n-1}\bigcup Q_{n-1}\bigcup xx^{1}\bigcup
yy^{1}\bigcup zz^{1}\bigcup w_{n-1}w_{n-1}^{1}$, then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Case $2$. $|S\bigcap V(D_{0i})|=3$ and $|S\bigcap V(D_{1j})|=1$ for
$i,j\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=3$ and $|S\bigcap
V(D_{11})|=1$. Let $\\{x,y,z\\}\subseteq V(D_{01})$ and $w\in V(D_{11})$. See
Figure $3$. Let $Y$ and $\widehat{T}_{i}$s for $1\leq i\leq n-2$ be the same
as case $1$. Note that $Y=\\{y_{1},y_{2},\ldots,y_{n-2}\\}$ and
$\widehat{T}_{1},\widehat{T}_{2},\cdots,\widehat{T}_{n-2}$ are $n-2$
internally disjoint trees connecting $x,y$ and $z$ in $D_{01}$. Let
$Y^{1}=\\{y_{1}^{1},y_{2}^{1},\ldots,y_{n-2}^{1}\\}$, where $y_{i}^{1}$ is the
outside neighbour of $y_{i}$ in $D_{n}$ for each $y_{i}\in Y$.

Subcase $2.1$. If no element in $Y^{1}$ belongs to $D_{11}$. Without loss of
generality, let $y_{i}^{1}\in V(D_{1(i+1)})$ for each
$i\in\\{1,2,\cdots,n-2\\}$. Let
$N_{D_{11}}(w)=\\{w_{1},w_{2},\cdots,w_{n-2},w_{n-1}\\}$. Then choose $n-2$
vertices from $N_{D_{11}}(w)$ such that none of them with outside neighbour in
$D_{01}$, say $w_{1},w_{2},\cdots,w_{n-2}$ and let
$W=\\{w_{1},w_{2},\cdots,w_{n-2}\\}$. Without loss of generality, let
$w_{i}^{0}\in V(D_{0(i+1)})$, where $w_{i}^{0}$ is the outside neighbour of
$w_{i}$ in $D_{n}$. By Theorem 2, $D_{n}[V(D_{0(i+1)})\bigcup V(D_{1(i+1)})]$
is connected. Then there is a path $Q_{i}$ between $w_{i}^{0}$ and $y_{i}^{1}$
in $D_{n}[V(D_{0(i+1)})\bigcup V(D_{1(i+1)})]$ for each
$i\in\\{1,2,\cdots,n-2\\}$. Let $T_{i}=\widehat{T}_{i}\bigcup Q_{i}\bigcup
y_{i}y_{i}^{1}\bigcup w_{i}w_{i}^{0}\bigcup\\\ w_{i}w$ for each
$i\in\\{1,2,\cdots,n-2\\}$. Then $n-2$ internally disjoint $S$-trees $T_{i}$s
for $1\leq i\leq n-2$ that connecting $x,y,z$ and $w$ are obtained. Let
$x^{1},y^{1},z^{1},w^{0}$ and $w_{n-1}^{0}$ be the outside neighbours of
$x,y,z,w$ and $w_{n-1}$ in $D_{n}$, respectively.

Subcase $2.1.1$. If one of $x^{1},y^{1}$ and $z^{1}$ belongs to $D_{11}$, say
$x^{1}$. By Lemma 2, $\kappa(D_{11})=n-1$. Then $D_{11}\setminus W$ is
connected. Then there is a path $Q$ between $x^{1}$ and $w$ in
$D_{11}\setminus W$.

If $x^{1}\neq w$. By Lemma 1(2), $\\{y^{1},z^{1},w^{0}\\}\subseteq
V(D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i})$. As
$2^{n-1}>n-1$ for $n\geq 4$. By Theorem 2,
$D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$ is connected. Then
there is a tree $\widetilde{T}_{n-1}$ connecting $y^{1},z^{1}$ and $w^{0}$ in
$D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$. Let
$T_{n-1}=xx^{1}\bigcup Q\bigcup ww^{0}\bigcup yy^{1}\bigcup
zz^{1}\bigcup\widetilde{T}_{n-1}$, then $n-1$ internally disjoint $S$-trees
$T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

If $x^{1}=w$. By Lemma 1(2), $\\{w_{n-1}^{0},y^{1},z^{1}\\}\subseteq
V(D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i})$. As
$2^{n-1}>n-1$ for $n\geq 4$. By Theorem 2,
$D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$ is connected. Then
there is a tree $\widetilde{T}_{n-1}$ connecting $y^{1},z^{1}$ and
$w_{n-1}^{0}$ in $D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$.
Let $T_{n-1}=xw\bigcup ww_{n-1}\bigcup
w_{n-1}w_{n-1}^{0}\bigcup\widetilde{T}_{n-1}\bigcup yy^{1}\bigcup zz^{1}$.
Then $n-1$ internally disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are
obtained in $D_{n}$.

Subcase $2.1.2$. If none of $x^{1},y^{1}$ and $z^{1}$ belongs to $D_{11}$.
Then $\\{x^{1},y^{1},z^{1}\\}\subseteq
V(D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i})$. By Lemma 1(2),
at least one of $w^{0}$ and $w_{n-1}^{0}$ does not belong to $D_{01}$.

If $w^{0}\notin V(D_{01})$, then $w^{0}\in
V(D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i})$. By Theorem 2,
$D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$ is connected. Then
there is a tree $\widetilde{T}_{n-1}$ connecting $x^{1},y^{1}$ and $z^{1}$ and
$w^{0}$ in $D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$. Let
$T_{n-1}=\widetilde{T}_{n-1}\bigcup xx^{1}\bigcup yy^{1}\bigcup zz^{1}\bigcup
ww^{0}$, then $n-1$ internally disjoint $S$-trees $T_{i}$s for $1\leq i\leq
n-1$ are obtained in $D_{n}$.

If $w_{n-1}^{0}\notin V(D_{01})$, then $w_{n-1}^{0}\in
V(D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i})$. By Theorem 2,
$D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$ is connected. Then
there is a tree $\widetilde{T}_{n-1}$ connecting $x^{1},y^{1}$ and $z^{1}$ and
$w_{n-1}^{0}$ in $D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$.
Let $T_{n-1}=\widetilde{T}_{n-1}\bigcup xx^{1}\bigcup yy^{1}\bigcup
zz^{1}\bigcup w_{n-1}w_{n-1}^{0}\bigcup ww_{n-1}$, then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Subcase $2.2$. If there is some element in $Y^{1}$ belongs to $D_{11}$.
Without loss of generality, let $y_{1}^{1}\in V(D_{11})$ and $y_{i}^{1}\in
V(D_{1i})$ for $2\leq i\leq n-2$. Define $W$ same as Subcase $2.1$. By Lemma
2, $\kappa(D_{11})=n-1$. Then $D_{11}\setminus W$ is connected. Then there is
a path $Q$ between $y_{1}^{1}$ and $w$ in $D_{11}\setminus W$. Then let
$T_{1}=\widehat{T}_{1}\bigcup y_{1}y_{1}^{1}\bigcup Q$. By Theorem 2,
$D_{n}[V(D_{0(i+1)})\bigcup V(D_{1i})]$ is connected. Then there is a path
$Q_{i}$ between $w_{i}^{0}$ and $y_{i}^{1}$ in $D_{n}[V(D_{0(i+1)})\bigcup
V(D_{1i})]$ for each $i\in\\{2,\cdots,n-2\\}$. Let
$T_{i}=\widehat{T}_{i}\bigcup Q_{i}\bigcup y_{i}y_{i}^{1}\bigcup
w_{i}w_{i}^{0}\bigcup w_{i}w$ for each $2\leq i\leq n-2$. Combining with
$T_{1}$, then $n-2$ internally disjoint $S$-trees $T_{i}$s for $1\leq i\leq
n-2$ that connecting $x,y,z$ and $w$ are obtained.

Subcase $2.2.1$. If $y_{1}^{1}\neq w$. By Lemma 1(2),
$\\{x^{1},y^{1},z^{1},w^{1}\\}\subseteq
V(D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i})$. As
$2^{n-1}>n-1$ for $n\geq 4$. By Theorem 2,
$D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$ is connected. Then
there is a tree $\widetilde{T}_{n-1}$ connecting $x^{1},y^{1}$ and $z^{1}$ and
$w^{1}$ in $D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$. Let
$T_{n-1}=\widetilde{T}_{n-1}\bigcup xx^{1}\bigcup yy^{1}\bigcup zz^{1}\bigcup
ww^{1}$, then $n-1$ internally disjoint $S$-trees $T_{i}$s for $1\leq i\leq
n-1$ are obtained in $D_{n}$.

Subcase $2.2.2$. If $y_{1}^{1}=w$. Then $T_{1}=\widehat{T}_{1}\bigcup
y_{1}y_{1}^{1}$. By Lemma 1(2), $\\{w_{n-1}^{0},x^{1},y^{1},z^{1}\\}\subseteq
V(D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i})$. As
$2^{n-1}>n-1$ for $n\geq 4$. By Theorem 2,
$D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$ is connected. Then
there is a tree $\widetilde{T}_{n-1}$ connecting $w_{n-1}^{0},x^{1},y^{1}$ and
$z^{1}$ in $D_{n}-\bigcup_{i=1}^{n-1}D_{0i}-\bigcup_{i=1}^{n-1}D_{1i}$. Let
$T_{n-1}=\widetilde{T}_{n-1}\bigcup xx^{1}\bigcup yy^{1}\bigcup zz^{1}\bigcup
ww_{n-1}\bigcup w_{n-1}w_{n-1}^{0}$, then $n-1$ internally disjoint $S$-trees
$T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Figure 3: The illustration of Subcase $2.1$

Case $3$. $|S\bigcap V(D_{0i})|=2$ and $|S\bigcap V(D_{0j})|=2$ for $i\neq j$
and $i,j\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=2$ and $|S\bigcap
V(D_{02})|=2$. Let $\\{x,y\\}\subseteq V(D_{01})$ and $\\{z,w\\}\subseteq
V(D_{02})$. Recall that $D_{ij}$ is a copy of $Q_{n-1}$. By Lemma 2,
$\kappa(D_{01})=\kappa(D_{02})=n-1$. Then there are $n-1$ internally disjoint
paths $P_{1},P_{2},\cdots,P_{n-1}$ between $x$ and $y$ in $D_{01}$ and $n-1$
internally disjoint paths
$P_{1}^{\prime},P_{2}^{\prime},\cdots,P_{n-1}^{\prime}$ between $z$ and $w$ in
$D_{02}$. Let $x_{i}\in V(P_{i})$ and $y_{i}\in V(P_{i}^{\prime})$ for each
$i\in\\{1,2,\cdots,n-1\\}$. Let $x_{i}^{1}$ and $y_{i}^{1}$ be the outside
neighbour of $x_{i}$ and $y_{i}$ in $D_{n}$ for each
$i\in\\{1,2,\cdots,n-1\\}$, respectively. Without loss of generality, let
$x_{i}^{1}\in V(D_{1i})$ for each $i\in\\{1,2,\cdots,n-1\\}$. Let
$X^{\prime}=\\{x_{1}^{1},x_{2}^{1},\cdots,x_{n-1}^{1}\\}$ and
$Y^{\prime}=\\{y_{1}^{1},y_{2}^{1},\cdots,y_{n-1}^{1}\\}$, then
$X^{\prime}\bigcap Y^{\prime}=\emptyset$.

Subcase $3.1$. If there is no vertex in $X^{\prime}$ belongs to the same
cluster with the vertices in $Y^{\prime}$. Then without loss of generality,
let $y_{i}^{1}\in V(D_{1(i+n-1)})$ for each $i\in\\{1,2,\cdots,n-1\\}$. This
can be done as $2^{n-1}>2(n-1)$ for $n\geq 4$. See Figure $4$. By Theorem 2,
$D_{n}[V(D_{1i})\bigcup V(D_{1(i+n-1)})\bigcup V(D_{0(i+n-1)})]$ is connected
for each $i\in\\{1,2,\cdots,n-1\\}$. Then there is a path $Q_{i}$ between
$x_{i}^{1}$ and $y_{i}^{1}$ in $D_{n}[V(D_{1i})\bigcup V(D_{1(i+n-1)})\bigcup
V(D_{0(i+n-1)})]$ for each $i\in\\{1,2,\cdots,n-1\\}$. Let $T_{i}=P_{i}\bigcup
P_{i}^{\prime}\bigcup Q_{i}\bigcup x_{i}x_{i}^{1}\bigcup y_{i}y_{i}^{1}$ for
each $i\in\\{1,2,\cdots,n-1\\}$. Then $n-1$ internally disjoint $S$-trees
$T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Subcase $3.2$. If there are some vertices in $X^{\prime}$ belong to the same
cluster with some vertices in $Y^{\prime}$. Then without loss of generality,
let $x_{i}^{1}$ and $y_{i}^{1}$ belong to the same cluster for $t\leq i\leq
n-1$ and let $y_{i}^{1}\in V(D_{1(i+n-1)})$ for $1\leq i\leq t-1$, where
$1\leq t\leq n-1$. By Theorem 2, $D_{n}[V(D_{1i})\bigcup
V(D_{1(i+n-1)})\bigcup V(D_{0(i+n-1)})]$ is connected for $1\leq i\leq t-1$.
Then there is a path $Q_{i}$ between $x_{i}^{1}$ and $y_{i}^{1}$ in
$D_{n}[V(D_{1i})\bigcup V(D_{1(i+n-1)})\bigcup V(D_{0(i+n-1)})]$ for each
$i\in\\{1,2,\cdots,t-1\\}$. As $x_{i},y_{i}\in V(D_{1i})$ and $D_{1i}$ is
connected for each $i\in\\{t,t+1,\cdots,n-1\\}$, then there is a path $R_{i}$
between $x_{i}$ and $y_{i}$ in $D_{1i}$ for $t\leq i\leq n-1$. Let
$T_{i}=P_{i}\bigcup P_{i}^{\prime}\bigcup Q_{i}\bigcup x_{i}x_{i}^{1}\bigcup
y_{i}y_{i}^{1}$ for $1\leq i\leq t-1$ and $T_{i}=P_{i}\bigcup
P_{i}^{\prime}\bigcup R_{i}\bigcup x_{i}x_{i}^{1}\bigcup y_{i}y_{i}^{1}$ for
$t\leq i\leq n-1$. Then $n-1$ internally disjoint trees $T_{i}$s for $1\leq
i\leq n-1$ are obtained in $D_{n}$.

Figure 4: The illustration of Subcase $3.1$

Case $4$. $|S\bigcap V(D_{0i})|=2$ and $|S\bigcap V(D_{1j})|=2$ for
$i,j\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=2$ and $|S\bigcap
V(D_{11})|=2$. Let $\\{x,y\\}\subseteq V(D_{01})$ and $\\{z,w\\}\subseteq
V(D_{11})$. See Figure $5$. Recall that $D_{ij}$ is a copy of $Q_{n-1}$. By
Lemma 2, $\kappa(D_{01})=\kappa(D_{11})=n-1$. Then there are $n-1$ internally
disjoint paths $P_{1},P_{2},\cdots,P_{n-1}$ between $x$ and $y$ in $D_{01}$
and $n-1$ internally disjoint paths
$P_{1}^{\prime},P_{2}^{\prime},\cdots,P_{n-1}^{\prime}$ between $z$ and $w$ in
$D_{11}$. Let $x_{i}\in V(P_{i})$ such that $x_{i}^{1}$, the outside neighbour
of $x_{i}$, does not belong to $D_{11}$. Without loss of generality, let
$x_{i}^{1}\in V(D_{1(i+1)})$. Similarly, let $y_{i}\in V(P_{i}^{\prime})$ such
that $y_{i}^{0}$, the outside neighbour of $y_{i}$, does not belong to
$D_{01}$. Without loss of generality, let $y_{i}^{0}\in V(D_{0(i+1)})$. This
can be done as $2^{n-1}>n$ for $n\geq 4$. By Theorem 2,
$D_{n}[V(D_{0(i+1)})\bigcup V(D_{1(i+1)})]$ is connected. Then there is a path
$Q_{i}$ between $x_{i}^{1}$ and $y_{i}^{0}$ in $D_{n}[V(D_{0(i+1)})\bigcup
V(D_{1(i+1)})]$ for each $i\in\\{1,2,\cdots,n-1\\}$. Let $T_{i}=P_{i}\bigcup
P_{i}^{\prime}\bigcup Q_{i}\bigcup x_{i}x_{i}^{1}\bigcup y_{i}y_{i}^{0}$ for
each $i\in\\{1,2,\cdots,n-1\\}$. Then $n-1$ internally disjoint $S$-trees
$T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Figure 5: The illustration of Case $4$

∎

######  Theorem 4.

Let $D_{n}$ be an $n$-dimensional dual cube and $S=\\{x,y,z,w\\}$, where
$x,y,z$ and $w$ are any four distinct vertices of $D_{n}$ for $n\geq 4$. If
the vertices in $S$ belong to three clusters of $D_{n}$, then there are $n-1$
internally disjoint trees connecting $S$ in $D_{n}$.

Proof. Let $D_{01},D_{02},\cdots,D_{02^{n-1}}$ be the clusters of class $0$
and $D_{11},D_{12},\cdots$ and $D_{12^{n-1}}$ be the clusters of class $1$ of
$D_{n}$. Let $S=\\{x,y,z,w\\}$, where $x,y,z$ and $w$ are any four distinct
vertices of $D_{n}$ for $n\geq 4$. Let the vertices in $S$ belong to three
clusters of $D_{n}$. By the symmetry of $D_{n}$, the following cases are
considered.

Case $1$. $|S\bigcap V(D_{0i})|=2$, $|S\bigcap V(D_{0j})|=1$ and $|S\bigcap
V(D_{0k})|=1$ for distinct $i,j,k\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=2,|S\bigcap
V(D_{02})|=1$ and $|S\bigcap V(D_{03})|=1$. Let $x,y\in V(D_{01}),z\in
V(D_{02})$ and $w\in V(D_{03})$. See Figure $6$. Recall that $D_{01}$ is a
copy of $Q_{n-1}$. By Lemma 2, $\kappa(D_{01})=n-1$. Then there are $n-1$
internally disjoint paths $P_{1},P_{2},\cdots,P_{n-1}$ between $x$ and $y$ in
$D_{01}$. Let $x_{i}\in V(P_{i})$ and $x_{i}^{1}$ be the outside neighbour of
$x_{i}$ in $D_{n}$ for $1\leq i\leq n-1$. Without loss of generality, let
$x_{i}^{1}\in V(D_{1i})$. Then choose $n-1$ vertices
$z_{1},z_{2},\cdots,z_{n-1}$ from $D_{02}$ such that $z_{i}^{1}$, the outside
neighbour of $z_{i}$, belongs to $D_{1i}$. Similarly, choose $n-1$ vertices
$w_{1},w_{2},\cdots,w_{n-1}$ from $D_{03}$ such that $w_{i}^{1}$, the outside
neighbour of $w_{i}$, belongs to $D_{1i}$ for each $i\in\\{1,2,\cdots,n-1\\}$.
Let $Z=\\{z_{1},z_{2},\cdots,z_{n-1}\\}$ and
$W=\\{w_{1},w_{2},\cdots,w_{n-1}\\}$. By Lemma 2,
$\kappa(D_{02})=\kappa(D_{03})=n-1$. By Lemma 5, there are $n-1$ internally
disjoint paths $Q_{1},Q_{2},\cdots,Q_{n-1}$ from $z$ to $Z$ in $D_{02}$ and
$n-1$ internally disjoint paths $R_{1},R_{2},\cdots,R_{n-1}$ from $w$ to $W$
in $D_{03}$. It is possible that one of the paths $Q_{i}s(R_{i}s)$ is a single
vertex. Let $X^{\prime}=\\{x_{i}^{1},z_{i}^{1},w_{i}^{1}\\}$, then
$X^{\prime}\subset V(D_{1i})$. As $D_{1i}$ is connected, then there is a
$X^{\prime}$-tree $\widehat{T}_{i}$ in $D_{1i}$ for each
$i\in\\{1,2,\cdots,n-1\\}$. Let $T_{i}=P_{i}\bigcup Q_{i}\bigcup
R_{i}\bigcup\widehat{T}_{i}\bigcup x_{i}x_{i}^{1}\bigcup z_{i}z_{i}^{1}\bigcup
w_{i}w_{i}^{1}$ for each $i\in\\{1,2,\cdots,n-1\\}$. Then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Figure 6: The illustration of Case $1$

Case $2$. $|S\bigcap V(D_{0i})|=2$, $|S\bigcap V(D_{0j})|=1$ and $|S\bigcap
V(D_{1k})|=1$ for $i\neq j$ and $i,j,k\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=2,|S\bigcap
V(D_{02})|=1$ and $|S\bigcap V(D_{11})|=1$. Let $\\{x,y\\}\subseteq
V(D_{01}),z\in V(D_{02})$ and $w\in V(D_{11})$. Recall that $D_{01}$ is a copy
of $Q_{n-1}$. By Lemma 2, $\kappa(D_{01})=n-1$. Then there are $n-1$
internally disjoint paths $P_{1},P_{2},\cdots,P_{n-1}$ between $x$ and $y$ in
$D_{01}$. See Figure $7$. Let $x_{i}\in V(P_{i})$ and $x_{i}^{1}$ be the
outside neighbour of $x_{i}$ in $D_{n}$ for each $i\in\\{1,2,\cdots,n-1\\}$.
Without loss of generality, let $x_{i}^{1}\in V(D_{1(i+1)})$. Choose $n-1$
vertices $z_{1},z_{2},\cdots,z_{n-1}$ from $D_{02}$ such that $z_{i}^{1}$, the
outside neighbour of $z_{i}$, belongs to $D_{1(i+1)}$ for each
$i\in\\{1,2,\cdots,n-1\\}$. Then choose $n-1$ vertices
$w_{1},w_{2},\cdots,w_{n-1}$ from $D_{11}$ such that $w_{i}^{0}$, the outside
neighbour of $w$, belongs to neither $D_{01}$ nor $D_{02}$. Without loss of
generality, let $w_{i}^{0}\in V(D_{0(i+2)})$. This can be done as
$2^{n-1}>n+1$ for $n\geq 4$. Let $W=\\{w_{1},w_{2},\cdots,w_{n-1}\\}$ and
$Z=\\{z_{1},z_{2},\cdots,z_{n-1}\\}$. By Lemma 5, there are $n-1$ internally
disjoint paths $Q_{1},Q_{2},\cdots,Q_{n-1}$ from $w$ to $W$ in $D_{11}$ and
$n-1$ internally disjoint paths $R_{1},R_{2},\cdots,R_{n-1}$ from $z$ to $Z$
in $D_{02}$. It is possible that one of the paths $Q_{i}s(Q_{i}s)$ is a single
vertex. By Theorem 2, $D_{n}[V(D_{1(i+1)})\bigcup V(D_{0(i+2)})]$ is
connected. Then there is a tree $\widehat{T}_{i}$ connecting
$x_{i}^{1},z_{i}^{1}$ and $w_{i}^{0}$ in $D_{n}[V(D_{1(i+1)})\bigcup
V(D_{0(i+2)})]$. Let $T_{i}=P_{i}\bigcup Q_{i}\bigcup
R_{i}\bigcup\widehat{T}_{i}\bigcup x_{i}x_{i}^{1}\bigcup z_{i}z_{i}^{1}\bigcup
w_{i}w_{i}^{0}$ for each $i\in\\{1,2,\cdots,n-1\\}$. Then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Figure 7: The illustration of Case $2$

Case $3$. $|S\bigcap V(D_{0i})|=2$, $|S\bigcap V(D_{1j})|=1$ and $|S\bigcap
V(D_{1k})|=1$ for $j\neq k$ and $i,j,k\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=2,|S\bigcap
V(D_{11})|=1$ and $|S\bigcap V(D_{12})|=1$. Let $\\{x,y\\}\subseteq
V(D_{01}),z\in V(D_{11})$ and $w\in V(D_{12})$. Recall that $D_{01}$ is
isomorphic to $Q_{n-1}$, then there are $n-1$ internally disjoint paths
$P_{1},P_{2},\cdots,P_{n-1}$ between $x$ and $y$ in $D_{01}$. See Figure $8$.

Subcase $3.1$. If there exists $x_{i}\in V(P_{i})$ such that $x_{i}^{1}$, the
outside neighbour of $x_{i}$, belongs to neither $D_{11}$ nor $D_{12}$ for
each path $P_{i}$ with $i\in\\{1,2,\cdots,n-1\\}$. Without loss of generality,
let $x_{i}^{1}\in(V(D_{1(i+2)})$. This can be done as $2^{n-1}>n+1$ for $n\geq
4$. Now, choose $n-1$ vertices $z_{1},z_{2},\cdots,z_{n-1}$ from
$D_{11}\setminus\\{z\\}$ such that $z_{i}^{0}$, the outside neighbour of
$z_{i}$, does not belong to $D_{01}$. Without loss of generality, let
$z_{i}^{0}\in V(D_{0(i+1)})$. Then choose $n-1$ vertices
$w_{1},w_{2},\cdots,w_{n-1}$ from $D_{12}\setminus\\{w\\}$ such that
$w_{i}^{0}$, the outside neighbour of $w_{i}$, belongs to $D_{0(i+1)}$ for
each $i\in\\{1,2,\cdots,n-1\\}$. Let $Z=\\{z_{1},z_{2},\cdots,z_{n-1}\\}$ and
$W=\\{w_{1},w_{2},\cdots,w_{n-1}\\}$. By Lemma 2,
$\kappa(D_{11})=\kappa(D_{12})=n-1$. By Lemma 5, there are $n-1$ internally
disjoint paths $Q_{1},Q_{2},\cdots,Q_{n-1}$ from $z$ to $Z$ in $D_{11}$ and
$n-1$ internally disjoint paths $R_{1},R_{2},\cdots,R_{n-1}$ from $w$ to $W$
in $D_{12}$. By Theorem 2, $D_{n}[V(D_{0(i+1)})\bigcup V(D_{1(i+2)})]$ is
connected for each $i\in\\{1,2,\cdots,n-1\\}$. Then there is a tree
$\widehat{T}_{i}$ connecting $z_{i}^{0},w_{i}^{0}$ and $x_{i}^{1}$ in
$D_{n}[V(D_{0(i+1)})\bigcup V(D_{1(i+2)})]$. Let $T_{i}=P_{i}\bigcup
Q_{i}\bigcup R_{i}\bigcup\widehat{T}_{i}\bigcup x_{i}x_{i}^{1}\bigcup
z_{i}z_{i}^{0}\bigcup w_{i}w_{i}^{0}$ for each $i\in\\{1,2,\cdots,n-1\\}$.
Then $n-1$ internally disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are
obtained in $D_{n}$.

Figure 8: The illustration of Subcase $3.1$

Subcase $3.2$. If not, then there is a path $P_{i}=xy$ with length one such
that $x^{1}\in V(D_{11}),y^{1}\in V(D_{12})$ or $x^{1}\in V(D_{12}),y^{1}\in
V(D_{11})$, where $x^{1}$ and $y^{1}$ are the outside neighbour of $x$ and
$y$, respectively. Without loss of generality, let $P_{n-1}=xy,x^{1}\in
V(D_{11})$ and $y^{1}\in V(D_{12})$. Let $x_{i}\in V(P_{i})$ and $x_{i}^{1}$
be the outside neighbour of $x_{i}$ for $1\leq i\leq n-2$. Without loss of
generality, let $x_{i}^{1}\in(V(D_{1(i+2)})$ for $1\leq i\leq n-2$. Let
$N_{D_{11}}(z)=\\{z_{1},z_{2},\cdots,z_{n-2},z_{n-1}\\}$,
$N_{D_{12}}(w)=\\{w_{1},w_{2},\cdots,w_{n-2},w_{n-1}\\}$,
$Z=\\{z_{1},z_{2},\cdots,z_{n-2}\\}$ and $W=\\{w_{1},w_{2},\cdots,w_{n-2}\\}$.
By Lemma 2, $\kappa(D_{11})=\kappa(D_{12})=n-1$. Then $D_{11}\setminus Z$ and
$D_{12}\setminus W$ are both connected. Then there is a path $Q$ between
$x^{1}$ and $z$ in $D_{11}\setminus Z$ and a path $R$ between $y^{1}$ and $w$
in $D_{12}\setminus W$. Let $T_{1}=P_{n-1}\bigcup xx^{1}\bigcup yy^{1}\bigcup
Q\bigcup R$. Let $z_{i}^{0}$ and $w_{i}^{0}$ be the outside neighbour of
$z_{i}$ and $w_{i}$, respectively. Without loss of generality, let
$z_{i}^{0}\in V(D_{0(i+1)})$. Let
$Z^{0}=\\{z_{1}^{0},z_{2}^{0},\cdots,z_{n-2}^{0}\\}$ and
$W^{0}=\\{w_{1}^{0},w_{2}^{0},\cdots,w_{n-2}^{0}\\}$. Then $Z^{0}\bigcap
W^{0}=\emptyset$.

If there is no vertex in $Z^{0}$ belongs to the same cluster with the vertices
in $W^{0}$. Then without loss of generality, let $w_{i}^{0}\in
V(D_{0(i+n-1)})$ for each $i\in\\{1,2,\cdots,n-2\\}$. This can be done as
$2^{n-1}>2(n-1)$ for $n\geq 4$. By Theorem 2, $D_{n}[V(D_{1(i+2)})\bigcup
V(D_{0(i+1)}\bigcup V(D_{0(i+n-1)}]$ is connected for each
$i\in\\{1,2,\cdots,n-2\\}$. Then there is a tree $\widehat{T}_{i}$ connecting
$z_{i}^{0},w_{i}^{0}$ and $x_{i}^{1}$ in $D_{n}[V(D_{1(i+2)})\bigcup
V(D_{0(i+1)}\bigcup V(D_{0(i+n-1)}]$ for each $i\in\\{1,2,\cdots,n-2\\}$. Let
$T_{i}=P_{i}\bigcup\widehat{T}_{i}\bigcup x_{i}x_{i}^{1}\bigcup
z_{i}z_{i}^{0}\bigcup w_{i}w_{i}^{0}\bigcup zz_{i}\bigcup ww_{i}$ for each
$i\in\\{1,2,\cdots,n-2\\}$. Combining with $T_{1}$, then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

If there are some vertices in $Z^{0}$ belong to the same cluster with some
vertices in $W^{0}$. Then without loss of generality, let $z_{i}^{0}$ and
$w_{i}^{0}$ belong to the same cluster for $t\leq i\leq n-2$ and let
$w_{i}^{0}\in V(D_{0(i+n-1)})$ for $1\leq i\leq t-1$, where $1\leq t\leq n-2$.
By Theorem 2, $D_{n}[V(D_{1(i+2)})\bigcup V(D_{0(i+1)})\bigcup
V(D_{0(i+n-1)})]$ is connected for $1\leq i\leq t-1$. Then there is a tree
$\widehat{T}_{i}$ connecting $z_{i}^{0},w_{i}^{0}$ and $x_{i}^{1}$ in
$D_{n}[V(D_{1(i+2)})\bigcup V(D_{0(i+1)})\bigcup V(D_{0(i+n-1)})]$ for each
$i\in\\{1,2,\cdots,t-1\\}$. As $z_{i}^{0},w_{i}^{0}\in V(D_{0(i+1)})$ and
$D_{n}[V(D_{1(i+2)})\bigcup V(D_{0(i+1)})]$ is connected for each
$i\in\\{t,t+1,\cdots,n-1\\}$, then there is a tree $\widehat{T}_{i}$
connecting $z_{i}^{0},w_{i}^{0}$ and $x_{i}^{1}$ in
$D_{n}[V(D_{1(i+2)})\bigcup V(D_{0(i+1)})]$ for each $t\leq i\leq n-2$. Let
$T_{i}=P_{i}\bigcup\widehat{T}_{i}\bigcup x_{i}x_{i}^{1}\bigcup
z_{i}z_{i}^{0}\bigcup zz_{i}\bigcup\\\ ww_{i}\bigcup w_{i}w_{i}^{0}$ for each
$i\in\\{1,2,\cdots,n-2\\}$. Combining with $T_{1}$, then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$. ∎

######  Theorem 5.

Let $D_{n}$ be an $n$-dimensional dual cube and $S=\\{x,y,z,w\\}$, where
$x,y,z$ and $w$ are any four distinct vertices of $D_{n}$ for $n\geq 4$. If
the vertices in $S$ belong to four clusters of $D_{n}$, then there are $n-1$
internally disjoint trees connecting $S$ in $D_{n}$.

Proof. Let $D_{01},D_{02},\cdots,D_{02^{n-1}}$ be the clusters of class $0$
and $D_{11},D_{12},\cdots$ and $D_{12^{n-1}}$ be the clusters of class $1$ of
$D_{n}$. Let $S=\\{x,y,z,w\\}$, where $x,y,z$ and $w$ are any four distinct
vertices of $D_{n}$ for $n\geq 4$. Let the vertices in $S$ belong to four
clusters of $D_{n}$. By the symmetry of $D_{n}$, the following cases are
considered.

Case $1$. $|S\bigcap V(D_{0i})|=1,|S\bigcap V(D_{0j})|=1,|S\bigcap
V(D_{0k})|=1$ and $|S\bigcap V(D_{0l})|=1$ for distinct
$i,j,k,l\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=1,|S\bigcap
V(D_{02})|=1,|S\bigcap V(D_{03})|=1$ and $|S\bigcap V(D_{04})|=1$. Let $x\in
V(D_{01}),y\in V(D_{02}),z\in V(D_{03})$ and $w\in V(D_{04})$. See Figure $9$.
Choose $n-1$ vertices $x_{1},x_{2},\cdots,x_{n-1}$ from
$D_{01}\setminus\\{x\\}$. Without loss of generality, let $x_{i}^{1}\in
V(D_{1i})$, where $x_{i}^{1}$ is the outside neighbour of $x_{i}$ in $D_{n}$.
Then choose $n-1$ vertices $y_{1},y_{2},\cdots,y_{n-1}$ from $D_{02}$, $n-1$
vertices $z_{1},z_{2},\cdots,z_{n-1}$ from $D_{03}$ and $n-1$ vertices
$w_{1},w_{2},\cdots,w_{n-1}$ from $D_{04}$ such that $y_{i}^{1},z_{i}^{1}$ and
$w_{i}^{1}$ all belong to $D_{1i}$, where $y_{i}^{1},z_{i}^{1}$ and
$w_{i}^{1}$ are the outside neighbour $y_{i},z_{i}$ and $w_{i}$, respectively.
Let
$X=\\{x_{1},x_{2},\cdots,x_{n-1}\\},Y=\\{y_{1},y_{2},\cdots,y_{n-1}\\},Z=\\{z_{1},z_{2},\cdots,z_{n-1}\\}$
and $W=\\{w_{1},w_{2},\cdots,w_{n-1}\\}$. By Lemma 5, there are $n-1$
internally disjoint paths $P_{1},P_{2},\cdots,P_{n-1}$ from $x$ to $X$ in
$D_{01}$, $n-1$ internally disjoint paths $Q_{1},Q_{2},\cdots,Q_{n-1}$ from
$y$ to $Y$ in $D_{02}$, $n-1$ internally disjoint paths
$R_{1},R_{2},\cdots,R_{n-1}$ from $z$ to $Z$ in $D_{03}$ and $n-1$ internally
disjoint paths $S_{1},S_{2},\cdots,S_{n-1}$ from $w$ to $W$ in $D_{04}$,
respectively. It is possible that one of the paths $Q_{i}s(R_{i}s,S_{i}s)$ is
a single vertex. As $D_{1i}$ is connected, there is tree $\widehat{T}_{i}$
connecting $x_{i}^{1},y_{i}^{1}$, $z_{i}^{1}$ and $w_{i}^{1}$ in $D_{1i}$ for
each $i\in\\{1,2,\cdots,n-1\\}$. Let $T_{i}=P_{i}\bigcup Q_{i}\bigcup
R_{i}\bigcup S_{i}\bigcup\widehat{T}_{i}\bigcup x_{i}x_{i}^{1}\bigcup
y_{i}y_{i}^{1}\bigcup z_{i}z_{i}^{1}\bigcup w_{i}w_{i}^{1}$ for each
$i\in\\{1,2,\cdots,n-1\\}$. Then $n-1$ internally disjoint $S$-trees $T_{i}$s
for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Figure 9: The illustration of Case $1$

Case $2$. $|S\bigcap V(D_{0i})|=1,|S\bigcap V(D_{0j})|=1,|S\bigcap
V(D_{0k})|=1$ and $|S\bigcap V(D_{1l})|=1$ for distinct $i,j,k$ and
$i,j,k,l\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=1,|S\bigcap
V(D_{02})|=1,|S\bigcap V(D_{03})|=1$ and $|S\bigcap V(D_{11})|=1$. Let $x\in
V(D_{01}),y\in V(D_{02}),z\in V(D_{03})$ and $w\in V(D_{11})$. See Figure
$10$. Choose $n-1$ vertices $x_{1},x_{2},\cdots,x_{n-1}$ from $D_{01}$.
Without loss of generality, let $x_{i}^{1}\in V(D_{1(i+3)})$, where
$x_{i}^{1}$ is the outside neighbour of $x_{i}$. Then choose $n-1$ vertices
$y_{1},y_{2},\cdots,y_{n-1}$ from $D_{02}$ and $n-1$ vertices
$z_{1},z_{2},\cdots,z_{n-1}$ from $D_{03}$ such that $y_{i}^{1},z_{i}^{1}\in
V(D_{1(i+3)})$, where $y_{i}^{1}$ and $z_{i}^{1}$ are the outside neighbour
$y_{i}$ and $z_{i}$ in $D_{n}$, respectively. Then choose $n-1$ vertices
$w_{1},w_{2},\cdots,w_{n-1}$ from $D_{11}$ such that $w_{i}^{0}$, the outside
neighbour of $w_{i}$, does not belong to $D_{01},D_{02}$ and $D_{03}$. Without
loss od generality, let $w_{i}^{0}\in V(D_{0(i+3)})$. This can be done as
$2^{n-1}>n+2$ for $n\geq 4$. Let
$X=\\{x_{1},x_{2},\cdots,x_{n-1}\\},Y=\\{y_{1},y_{2},\cdots,y_{n-1}\\},Z=\\{z_{1},z_{2},\cdots,z_{n-1}\\}$
and $W=\\{w_{1},w_{2},\cdots,w_{n-1}\\}$. By Lemma 5, there are $n-1$
internally disjoint paths $P_{1},P_{2},\cdots,P_{n-1}$ from $x$ to $X$ in
$D_{01}$, $n-1$ internally disjoint paths $Q_{1},Q_{2},\cdots,Q_{n-1}$ from
$y$ to $Y$ in $D_{02}$, $n-1$ internally disjoint paths
$R_{1},R_{2},\cdots,R_{n-1}$ from $z$ to $Z$ in $D_{03}$ and $n-1$ internally
disjoint paths $S_{1},S_{2},\cdots,S_{n-1}$ from $w$ to $W$ in $D_{11}$,
respectively. It is possible that one of the paths
$P_{i}s(Q_{i}s,R_{i}s,S_{i}s)$ is a single vertex. By Theorem 2,
$D_{n}[V(D_{1(i+3)})\bigcup V(D_{0(i+3)})]$ is connected. Then there is tree
$\widehat{T}_{i}$ connecting $x_{i}^{1},y_{i}^{1}$, $z_{i}^{1}$ and
$w_{i}^{0}$ in $D_{n}[V(D_{1(i+3)})\bigcup V(D_{0(i+3)})]$. Let
$T_{i}=P_{i}\bigcup Q_{i}\bigcup R_{i}\bigcup S_{i}\bigcup\widehat{T}_{i}\\\
\bigcup x_{i}x_{i}^{1}\bigcup y_{i}y_{i}^{1}\bigcup z_{i}z_{i}^{1}\bigcup
w_{i}w_{i}^{0}$ for each $i\in\\{1,2,\cdots,n-1\\}$. Then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Figure 10: The illustration of Case $2$

Case $3$. $|S\bigcap V(D_{0i})|=1,|S\bigcap V(D_{0j})|=1,|S\bigcap
V(D_{1k})|=1$ and $|S\bigcap V(D_{1l})|=1$ for $i\neq j$, $k\neq l$ and
$i,j,k,l\in\\{1,2,\cdots,2^{n-1}\\}$.

Without loss of generality, let $|S\bigcap V(D_{01})|=1,|S\bigcap
V(D_{02})|=1,|S\bigcap V(D_{11})|=1$ and $|S\bigcap V(D_{12})|=1$. Let $x\in
V(D_{01}),y\in V(D_{02}),z\in V(D_{11})$ and $w\in V(D_{12})$. See Figure
$11$. Choose $n-1$ vertices $x_{1},x_{2},\cdots,x_{n-1}$ from $D_{01}$.
Without loss of generality, let $x_{i}^{1}\in V(D_{1(i+2)})$, where
$x_{i}^{1}$ is the outside neighbour of $x_{i}$ for $1\leq i\leq n-1$. Then
choose $n-1$ vertices $y_{1},y_{2},\cdots,y_{n-1}$ from $D_{02}$ such that
$y_{i}^{1}\in V(D_{1(i+2)})$, where $y_{i}^{1}$ is the outside neighbour of
$y_{i}$. Similarly, choose $n-1$ vertices $z_{1},z_{2},\cdots,z_{n-1}$ from
$D_{11}$. Without loss of generality, let $z_{i}^{0}\in V(D_{0(i+2)})$, where
$z_{i}^{0}$ is the outside neighbour of $z_{i}$ for $1\leq i\leq n-1$. Then
choose $n-1$ vertices $w_{1},w_{2},\cdots,w_{n-1}$ from $D_{12}$ such that
$w_{i}^{0}\in V(D_{0(i+2)})$, where $w_{i}^{0}$ is the outside neighbour of
$w_{i}$. Let
$X=\\{x_{1},x_{2},\cdots,x_{n-1}\\},Y=\\{y_{1},y_{2},\cdots,y_{n-1}\\},Z=\\{z_{1},z_{2},\cdots,z_{n-1}\\}$
and $W=\\{w_{1},w_{2},\cdots,w_{n-1}\\}$. By Lemma 5, there are $n-1$
internally disjoint paths $P_{1},P_{2},\cdots,P_{n-1}$ from $x$ to $X$ in
$D_{01}$, $n-1$ internally disjoint paths $Q_{1},Q_{2},\cdots,Q_{n-1}$ from
$y$ to $Y$ in $D_{02}$, $n-1$ internally disjoint paths
$R_{1},R_{2},\cdots,R_{n-1}$ from $z$ to $Z$ in $D_{11}$ and $n-1$ internally
disjoint paths $S_{1},S_{2},\cdots,S_{n-1}$ from $w$ to $W$ in $D_{12}$,
respectively. It is possible that one of the paths
$P_{i}s(Q_{i}s,R_{i}s,S_{i}s)$ is a single vertex. By Theorem 2,
$D_{n}[V(D_{0(i+2)})\bigcup V(D_{1(i+2)})]$ is connected for each
$i\in\\{1,2,\cdots,n-1\\}$. Then there is tree $\widehat{T}_{i}$ connecting
$x_{i}^{1},y_{i}^{1}$, $z_{i}^{0}$ and $w_{i}^{0}$ in
$D_{n}[V(D_{0(i+2)})\bigcup V(D_{1(i+2)})]$. Let $T_{i}=P_{i}\bigcup
Q_{i}\bigcup R_{i}\bigcup S_{i}\bigcup\widehat{T}_{i}\bigcup
x_{i}x_{i}^{1}\bigcup y_{i}y_{i}^{1}\bigcup z_{i}z_{i}^{0}\bigcup
w_{i}w_{i}^{0}$ for each $i\in\\{1,2,\cdots,n-1\\}$. Then $n-1$ internally
disjoint $S$-trees $T_{i}$s for $1\leq i\leq n-1$ are obtained in $D_{n}$.

Figure 11: The illustration of Case $3$

∎

######  Theorem 6.

Let $D_{n}$ be an $n$-dimensional dual cube, then $\kappa_{4}(D_{n})=n-1$ for
$n\geq 4$.

Proof. As $D_{n}$ is $n$ regular, by Lemma 4,
$\kappa_{4}(D_{n})\leq\delta-1=n-1.$ To prove the result, we just need to show
that $\kappa_{4}(D_{n})\geq n-1.$

Let $D_{01},D_{02},\cdots,D_{02^{n-1}}$ be the clusters of class $0$ and
$D_{11},D_{12},\cdots$ and $D_{12^{n-1}}$ be the clusters of class $1$ of
$D_{n}$. Let $x,y,z$ and $w$ be any four distinct vertices of $D_{n}$. For
convenience, let $S=\\{x,y,z,w\\}.$ By the symmetry of $D_{n}$, we prove the
result by considering the following cases.

Case 1. $x,y,z$ and $w$ belong the same cluster of $D_{n}$.

Without loss of generality, let $S\subseteq V(D_{01})$. Recall that $D_{01}$
is a copy of $Q_{n-1}$. By Theorem 1, $\kappa_{4}(Q_{n-1})=n-2$. Then there
are $(n-2)$-internally disjoint $S$-trees $T_{1},T_{2},\cdots,T_{n-2}$ in
$D_{01}$. Let $x^{1},y^{1},z^{1}$ and $w^{1}$ be the outside neighbours of
$x,y,z$ and $w$ in $D_{n}$. By Lemma 1,
$\\{x^{1},y^{1},z^{1},w^{1}\\}\subseteq V(D_{n}\setminus D_{01})$. By Theorem
2, $D_{n}\setminus D_{01}$ is connected. Thus, there is a tree
$\widehat{T}_{n-1}$ connecting $x^{1},y^{1},z^{1}$ and $w^{1}$ in
$D_{n}\setminus D_{01}$. Let $T_{n-1}=\widehat{T}_{n-1}\bigcup xx^{1}\bigcup
yy^{1}\bigcup zz^{1}\bigcup ww^{1}$, then $T_{1},T_{2},\cdots,T_{n-1}$ are
$(n-1)$-internally disjoint $S$-trees in $D_{n}$ and the result is desired.

Case 2. $x,y,z$ and $w$ belong to two different clusters of $D_{n}$.

By Theorem 3, $(n-1)$-internally disjoint $S$-trees
$T_{1},T_{2},\cdots,T_{n-1}$ can be obtained in $D_{n}$.

Case 3. $x,y,z$ and $w$ belong to three different clusters of $D_{n}$.

By Theorem 4, $(n-1)$-internally disjoint $S$-trees
$T_{1},T_{2},\cdots,T_{n-1}$ can be obtained in $D_{n}$.

Case 4. $x,y,z$ and $w$ belong to four different clusters of $D_{n}$.

By Theorem 5, $(n-1)$-internally disjoint $S$-trees
$T_{1},T_{2},\cdots,T_{n-1}$ can be obtained in $D_{n}$.

Thus, $\kappa_{4}(D_{n})\geq n-1$ and the result is desired. ∎

By Theorem 6 and Lemma 3, we have the following corollary.

######  Corollary 1.

Let $D_{n}$ be an $n$-dimensional dual cube. Then $\kappa_{3}(D_{n})=n-1$ for
$n\geq 4$.

##  4 The $r$-component connectivity of dual cubes

In this section, we prove the $r$-component connectivity $c\kappa_{r}(D_{n})$
of $D_{n}$. To prove the result, the following result is useful.

######  Lemma 6.

([26]) Any two vertices in $V(Q_{n})$ have exactly two common neighbours for
$n\geq 3$ if they have any.

######  Theorem 7.

([1]) Let $n$ and $k$ be positive integers such that $n\geq 3$ and $1\leq
k\leq n-1$. Let $D_{n}$ be a dual cube network of order $n$ and $T\subseteq
V(D_{n})$. If $|T|\leq kn-\frac{k(k+1)}{2}$, then $D_{n}-T$ is either
connected or it has a large connected component and small components with at
most $k-1$ vertices in total. Moreover, there is a set of vertices $T$ in
$D_{n}$ such that $|T|=kn-\frac{k(k+1)}{2}+1$ and $D_{n}-T$ has a component
containing exactly $k$ vertices.

Following, we show the $r$-component connectivity of the dual cube $D_{n}$.

######  Theorem 8.

Let $D_{n}$ be the $n$-dimensional dual cube, then
$c\kappa_{r+1}(D_{n})=rn-\frac{r(r+1)}{2}+1$ for $n\geq 2$ and $1\leq r\leq
n-1$.

Proof. By Theorem 7, $c\kappa_{r+1}(D_{n})\geq rn-\frac{r(r+1)}{2}+1$.
Following, we show that $c\kappa_{r+1}(D_{n})\leq rn-\frac{r(r+1)}{2}+1$. Let
$u\in V(D_{01})$, then $u$ has $n-1$ neighbours $u_{1},u_{2},\cdots,$ and
$u_{n-1}$ in $D_{01}$ as $D_{01}$ is a copy of $Q_{n-1}$. As $D_{n}$ is
bipartite, then $u_{i}$ and $u_{j}$ are non-adjacent for $i\neq j$ and
$i,j\in\\{1,2,\cdots,n-1\\}$. Let $1\leq r\leq n-1$ and
$S=N_{D_{n}}(\\{u_{1},u_{2},\cdots,u_{r}\\})$. Then $u\in S$. By Lemma 6,
$|S|=r(n-1)-\frac{r(r+1)}{2}+1+r=rn-\frac{r(r+1)}{2}+1$. It is obvious that
$D_{n}-S$ contains at least $r+1$ components, where at least $r$ of them are
singletons. Hence, $c\kappa_{r+1}(D_{n})\leq rn-\frac{r(r+1)}{2}+1$. Combining
with $c\kappa_{r+1}(D_{n})\geq rn-\frac{r(r+1)}{2}+1$, we have that
$c\kappa_{r+1}(D_{n})=rn-\frac{r(r+1)}{2}+1$ for $n\geq 2$ and $1\leq r\leq
n-1$. ∎

##  5 Concluding remarks

The dual cube has some attractive properties to design interconnection
networks. In this paper, we focus on the dual cube, which is an invariant of
the hypercube and denoted by $D_{n}$. We first show that
$\kappa_{4}(D_{n})=n-1$ for $n\geq 4$. That is, for any four vertices in
$D_{n}$, there are $n-1$ internally disjoint trees connecting them in $D_{n}$.
As a corollary, we obtain $\kappa_{3}(D_{n})=n-1$ for $n\geq 4$. Furthermore,
we show that $c\kappa_{r+1}(D_{n})=rn-\frac{r(r+1)}{2}+1$ for $n\geq 2$ and
$1\leq r\leq n-1$. So far, the results about the generalized $k$-connectivity
of networks are almost about $k=3$ and there are few results about larger $k$.
We are interested in this topic and we would like to study the generalized
$k$-connectivity of the dual cube for $k\geq 5$ in the future. In addition, we
conjecture that $\kappa_{r}(D_{n})=n-1$ for $5\leq r\leq n$ and $n\geq 2$. We
would like to prove the result for the dual cube and show the corresponding
results for other classical networks such as arrangement graphs, balanced
graphs, $(n,k)$-star networks and so on.

## Acknowledgments

This work was supported by the National Natural Science Foundation of China
(Nos.11371052, 11731002, 11571035), the Fundamental Research Funds for the
Central Universities (No. 2016JBM071, 2016JBZ012) and the $111$ Project of
China (B16002).

## References

  * [1] A. Angjeli, E.Cheng and L. Liptak, Linearly many faults in dual-cube-like networks, Theoretical computer science 472 (2013) 1-8.
  * [2] J. Bondy and U. Murty, Graph Theory, Springer, 2008.
  * [3] G. Chartrand, S.F. Kapoor, L. Lesniak, D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1-6.
  * [4] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (4) (2010) 360-367.
  * [5] L.-H. Hsu, E. Cheng, L. Liptak, J.M. Tan, C-K Lin and T-Y Ho, Component connectivity of the hypercubes, International Journal of Computer Mathematics 89 (2012) 137-145.
  * [6] H. Li, X. Li and Y. Sun, The generalized $3$-connectivity of Cartesian product graphs, Discret. Math. Theor. Comput. Sci. 14 (1) (2012) 43-54.
  * [7] S. Li, Y. Shi and J. Tu, The generalized $3$-connectivity of Cayley graphs on Symmetric Groups generated by trees and cycles. Graphs and Combinatorics 33 (2017) 1195-1209.
  * [8] H. Li, X. Li, Y. Mao and Y. Sun, Note on the generalized connectivity, Ars Comb. 114 (2014) 193-202.
  * [9] S. Li, J. Tu and C. Yu, The generalized $3$-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput. 274 (2016) 41-46.
  * [10] S. Li and X. Li, Note on the hardness of generalized connectivity, J. Comb. Optim. 24 (2012) 389-396.
  * [11] H. Li, Y. Ma, W. Yang and Y. Wang, The generalized $3$-connectivity of graph products, Appl. Math. Comput. 295 (2017) 77-83.
  * [12] S. Li, X. Li and W. Zhou, Sharp bounds for the generalized connectivity $\kappa_{3}(g)$, Discret. Math. 310 (2010) 2147-2163.
  * [13] S. Li, W. Li and X. Li, The generalized connectivity of complete bipartite graphs, Ars Comb. 104 (2012) 65-79.
  * [14] S. Lin and Q. Zhang, The generalized $4$-connectivity of hypercubes, Discret. Appl. Math. 220 (2017) 60-67.
  * [15] S. Lakshmivarahan, J. Jwo and S. Dhall, Symmetric in interconnection networks based on Caylay graphs of permutation groups: a survy, Parallel Comput. 19(1993) 361-407.
  * [16] S, Latifi and P. Srimani, Transposotion networks as a class of fault tolerant robust networks, Computer Science Technical Report, Computer Science Department, Colorado State University, 1995.
  * [17] H.-Z. Shi, G. Wang, J. Ma and F. Hou, One variety conjectures of complete-transposition network, Comput. Sci. 39 (2012) 404-407.
  * [18] H.-Z. Shi and J.-B. Lu, On conjectures of interconnection networks, Comput. Eng. Appl. 44 (2008) 199-200.
  * [19] J. Tu, Y. Zhou and G. Su, A kind of conditional connectivity of Cayley graphs generated by wheel graphs, App. Math. Comput. 301 (2017) 177-186.
  * [20] H. Whitney, Congruent graphs and connectivity of graphs, J. Amer. Math. Soc. 54 (1932) 150-168.
  * [21] M. Wan and Z. Zhang, A kind of conditional connectivity of star graphs, Appl. Math. Lett. 22 (2009) 264-267.
  * [22] G. Wang, H. Shi, F. Hou and Y. Bai, Some conditional vertex connectivities of complete transposition graphs, Inf. Sci. 295 (2015) 536-543.
  * [23] X. Yang and S. Zhou, On conditional fault tolerant of dual-cubes, International Journal of Parallel, Emergent and Distributed Systems, 28 (2013) 199-213.
  * [24] X. Yang and S. Zhou, On conditional fault tolerant of dual-cubes, International Journal of Parallel, Emergent and Distrib. Syst. 28(3) (2013), pp. 199-213.
  * [25] S. Zhao, W. Yang and S. Zhang, Component connectivity of hypercubes, Theoretical Computer Science. 640 (2016) 115-118.
  * [26] Q. Zhu and J. Xu, On restricted edge connectivity and extra edge connectivity of hypercubes and folded hypercubes, J. Univ. Sci. Technol. China 36 (3) (2006) 246-253.


* Bredies and Lorenz (2018) Kristian Bredies and Dirk Lorenz.  _Variational Methods_ , pages 251–443.  Springer International Publishing, 2018.
  * Bubeck (2015) Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends in Machine Learning_ , 8:231–357, 2015.
  * Cam (1990) Lucien Le Cam.  Maximum likelihood: An introduction.  _International Statistical Review_ , 58(2):153–171, 1990.
  * Casella (2001) George Casella.  Empirical Bayes Gibbs sampling.  _Biostatistics_ , 2(4):485–500, 12 2001.
  * Chambolle et al. (2018) Antonin Chambolle, Matthias J. Ehrhardt, Peter Richtárik, and Carola-Bibiane Schönlieb.  Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications.  _SIAM Journal on Optimization_ , 28(4):2783–2808, 2018.
  * Chen et al. (2020) Feiyu Chen, David Sondak, Pavlos Protopapas, Marios Mattheakis, Shuheng Liu, Devansh Agarwal, and Marco Di Giovanni.  Neurodiffeq: A python package for solving differential equations with neural networks.  _Journal of Open Source Software_ , 5(46), 2020.
  * Cherief-Abdellatif (2019) Badr-Eddine Cherief-Abdellatif.  Consistency of elbo maximization for model selection.  In _Proceedings of The 1st Symposium on Advances in Approximate Bayesian Inference_ , volume 96, pages 11–31. PMLR, 2019.
  * Cloez and Hairer (2015) Bertrand Cloez and Martin Hairer.  Exponential ergodicity for Markov processes with random switching.  _Bernoulli_ , 21(1):505–536, 2015.
  * Cohen et al. (2019) Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.  Certified adversarial robustness via randomized smoothing.  In _Proceedings of the 36th International Conference on Machine Learning (ICML 2019)_ , pages 1310–1320, 2019.
  * de Wiljes et al. (2018) Jana de Wiljes, Sebastian Reich, and Wilhelm Stannat.  Long-time stability and accuracy of the ensemble kalman–bucy filter for fully observed processes and small measurement noise.  _SIAM Journal on Applied Dynamical Systems_ , 17(2):1152–1181, 2018.
  * Defazio et al. (2014) Aaron Defazio, Francis Bach, and Simon Lacoste-Julien.  Saga: A fast incremental gradient method with support for non-strongly convex composite objectives.  In _Advances in Neural Information Processing Systems_ , pages 1646–1654, 2014.
  * Deqing and Sergei (2015) Huang Deqing and Chernyshenko Sergei.  Long-time average cost control of stochastic systems using sum of squares of polynomials.  In _2015 34th Chinese Control Conference (CCC)_ , pages 2344–2349, 2015.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12:2121–2159, 2011\.
  * Eftekhari et al. (2021) Armin Eftekhari, Bart Vandereycken, Gilles Vilmart, and Konstantinos C. Zygalakis.  Explicit stabilised gradient descent for faster strongly convex optimisation.  _Bit Numer Math_ , 61:119–139, 2021.
  * Gillespie (1977) Daniel T. Gillespie.  Exact stochastic simulation of coupled chemical reactions.  _The Journal of Physical Chemistry_ , 81(25):2340–2361, 1977.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * Hansen (2010) Per Christian Hansen.  _Discrete Inverse Problems_.  Society for Industrial and Applied Mathematics, 2010.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations, ICLR_ , 2015.
  * Kovachki and Stuart (2021) Nikola B. Kovachki and Andrew M. Stuart.  Continuous time analysis of momentum methods.  _Journal of Machine Learning Research_ , 22(17):1–40, 2021.
  * Kushner (1984) Harold Kushner.  _Approximation and Weak Convergence Methods for Random Processes, with Applications to Stochastic Systems Theory_ , volume 6 of _MIT Press Series in Signal Processing, Optimization, and Control_.  MIT Press, Cambridge, 1984.
  * Kushner (1990) Harold Kushner.  _Weak Convergence Methods and Singularly Perturbed Stochastic Control and Filtering Problems_.  Birkhäuser Basel, 1990.
  * Kushner and Yin (2003) Harold Kushner and George Yin.  _Stochastic Approximation Algorithms and Recursive Algorithms and Applications_.  Springer, New York, NY, 2003.
  * Latz (2021) Jonas Latz.  Analysis of stochastic gradient descent in continuous time.  _Statistics and Computing_ , 31(39), 2021.
  * Li et al. (2017) Qianxiao Li, Cheng Tai, and Weinan E.  Stochastic modified equations and adaptive stochastic gradient algorithms.  In _Proceedings of the 34th International Conference on Machine Learning (ICML 2017)_ , pages 2101–2110, 2017.
  * Li et al. (2019) Qianxiao Li, Cheng Tai, and Weinan E.  Stochastic modified equations and dynamics of stochastic gradient algorithms I: Mathematical foundations.  _Journal of Machine Learning Research_ , 20(40):1–47, 2019.
  * Li et al. (2021) Zongyi Li, Nikola Borislavov Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar.  Fourier neural operator for parametric partial differential equations.  In _International Conference on Learning Representations, ICLR_ , 2021.
  * Liggett (2010) Thomas Liggett.  _Continuous Time Markov Processes: An Introduction_.  American Mathematical Soc., 2010.
  * Lindgren et al. (2011) Finn Lindgren, Håvard Rue, and Johan Lindström.  An explicit link between gaussian fields and gaussian markov random fields: the stochastic partial differential equation approach.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 73(4):423–498, 2011.
  * Liu (1995) Yingjie Liu.  Discretization of a class of reflected diffusion processes.  _Mathematics and Computers in Simulation_ , 38(1):103–108, 1995.
  * Lord et al. (2014) Gabriel J. Lord, Catherine E. Powell, and Tony Shardlow.  _An Introduction to Computational Stochastic PDEs_.  Cambridge University Press, 2014.
  * Lu et al. (2021) Lu Lu, Xuhui Meng, Zhiping Mao, and George Em Karniadakis.  Deepxde: A deep learning library for solving differential equations.  _SIAM Review_ , 63(1):208–228, 2021.
  * Mandt et al. (2016) Stephan Mandt, Matthew D. Hoffman, and David M. Blei.  A variational analysis of stochastic gradient algorithms.  In _Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML 2016)_ , pages 354–363, 2016\.
  * Mandt et al. (2017) Stephan Mandt, Matthew D. Hoffman, and David M. Blei.  Stochastic Gradient Descent as Approximate Bayesian Inference.  _Journal of Machine Learning Research_ , 18(1):4873–4907, 2017.
  * May et al. (2013) Sandra May, Rolf Rannacher, and Boris Vexler.  Error analysis for a finite element approximation of elliptic dirichlet boundary control problems.  _SIAM Journal on Control and Optimization_ , 51(3):2585–2611, 2013.
  * Nemirovski et al. (2009) Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on Optimization_ , 19(4):1574–1609, 2009.
  * Pedro et al. (2019) Juan B. Pedro, Juan Maronas, and Roberto Paredes.  Solving partial differential equations with neural networks.  _arXiv:1912.04737_ , 2019.
  * Pettersson (1995) Roger Pettersson.  Approximations for stochastic differential equations with reflecting convex boundaries.  _Stochastic Processes and their Applications_ , 59:295–308, 1995.
  * Pinto et al. (2017) Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta.  Robust adversarial reinforcement learning.  In _Proceedings of the 34th International Conference on Machine Learning (ICML 2017)_ , page 2817–2826, 2017.
  * Quarteroni et al. (2007) Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri.  _Numerical Solution of Ordinary Differential Equations_ , pages 479–538.  Springer Berlin Heidelberg, 2007.
  * Raissi et al. (2019) Maziar Raissi, Paris Perdikaris, and George Em Karniadakis.  Physics-informed neural networks: a deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations.  _Journal of Computational Physics_ , 378:686–707, 2019\.
  * Revuz and Yor (2013) Daniel Revuz and Marc Yor.  _Continuous Martingales and Brownian Motion_.  Grundlehren der mathematischen Wissenschaften. Springer, Berlin, Heidelberg, 2013.
  * Robbins and Monro (1951) Herbert Robbins and Sutton Monro.  A Stochastic Approximation Method.  _The Annals of Mathematical Statistics_ , 22(3):400–407, 1951.
  * Robert and Casella (2004) Christian P. Robert and George Casella.  _Monte Carlo Statistical Methods_.  Springer New York, 2004.
  * Shorten and Khoshgoftaar (2019) Connor Shorten and Taghi M. Khoshgoftaar.  A survey on image data augmentation for deep learning.  _Journal of Big Data_ , 6(1):60, Jul 2019.
  * Sinova et al. (2018) Beatriz Sinova, Gil González-Rodríguez, and Stefan Van Aelst.  M-estimators of location for functional data.  _Bernoulli_ , 24(3):2328–2357, 2018.
  * Sirignano and Spiliopoulos (2017) Justin Sirignano and Konstantinos Spiliopoulos.  Stochastic gradient descent in continuous time.  _SIAM Journal on Financial Mathematics_ , 8(1):933–961, 2017.
  * Sirignano and Spiliopoulos (2018) Justin Sirignano and Konstantinos Spiliopoulos.  Dgm: A deep learning algorithm for solving partial differential equations.  _Journal of Computational Physics_ , 375:1339–1364, 2018\.
  * Smith et al. (2021) Samuel L. Smith, Benoit Dherin, David G. T. Barrett, and Soham De.  On the origin of implicit regularization in stochastic gradient descent.  In _International Conference on Learning Representations, ICLR_ , 2021.
  * Sutton and Barto (2018) Richard S. Sutton and Andrew G. Barto.  _Reinforcement Learning: An Introduction_.  MIT Press, 2018.
  * Trillos and Sanz-Alonso (2020) Nicolas Garcia Trillos and Daniel Sanz-Alonso.  The Bayesian Update: Variational Formulations and Gradient Flows.  _Bayesian Analysis_ , 15(1):29–56, 2020.
  * Wojtowytsch (2021) Stephan Wojtowytsch.  Stochastic gradient descent with noise of machine learning type. part II: Continuous time analysis.  _arXiv:2106.02588_ , 2021.