Structure connectivity and substructure connectivity of data center network

1.   Introduction

The topological structure of a computer interconnection network can be represented by a graph, where the vertices represent processors and the edges represent communication links between processors. The connectivity of a graph is an important parameter reflecting the strength between two nodes in an interconnection network. The connectivity of a graph $G$, denoted by $\kappa(G)$, is to delete the minimum number of vertices such that the remaining part is disconnected. The classical connectivity has certain limitations to measure the fault tolerance of the network, then Harary ^[6] proposed the concept of the conditional connectivity. Later, Fàbrega et al. ^[3] proposed the concept of the $g$-extra connectivity. The $g$-extra connectivity of $G$, denoted by $\kappa_g{(G)}$, is the minimum cardinality of vertices in $G$ whose deletion would disconnect $G$, and each remaining component has more than $g$ vertices. It has triggered extensive research by scholars, and some results can be found in ^{[2,5,7,13,18,21]}.

With the development of large-scale integration technology, a multi-processor system can contain thousands of processors. When one of the processors fails, the processors around it may all be affected. Therefore, it is necessary to consider deleting a certain structure in a network to measure the reliability of the network. Considering the fault status of a certain structure, rather than individual vertices, Lin et al. ^[10] have given the concepts of the structure connectivity and substructure connectivity. Recently, the results on the structure connectivity and substructure connectivity have come out focusing on networks. For example: hypercube network, folded hypercube network, star network, alternating group network and so on. Many results of networks can be found in the literature^{[8,9,10,11,12,14,15,16,19,20]}.

A network may have thousands of substructures, so it is an important topic to study which substructures are more valuable for the network reliability. A star as a substructure of a network is very important. Because when the central node fails, all of its neighbors are affected. It is reasonable to assume that a node in a network has different degrees of influence on its surrounding nodes. Therefore, we can assign an impactability to each node $v$, denoted by $imp(v)$. When $imp(v) = 0$, it means that $v$ has no effect on its neighbors; $imp(v) = 1$ means that $v$ affects all its direct neighbors; $imp(v) = 2$ means that $v$ affects not only all of its direct neighbors, but also its immediate neighbor's neighbors. In a network, the structure corresponding to the node $v$ with $imp(v) = 1$ is an $m$-leaves star with $v$ as the center, denoted by $S_m$. For $v$ with $imp(v) = 2$, its corresponding structure is called a $2$-step star with $m$-leaves, denoted by $S_{2m}$, centered on $v$. (See Figure 1.)

2.   Preliminaries

2.1.   Basic notations and definitions

Given a graph $G$, let $V(G)$, $E(G)$ and $(u, v)$ denote the set of vertices, the set of edges, and the edge whose end vertices are $u$ and $v$. The degree of the vertex $u$ in graph $G$ is the number of neighbors of $u$, denoted by $d(u)$. The neighbors of a vertex $u$ in $G$ is denoted by $N_G(u)$. For a set $U\subseteq V(G)$, the neighbors in $V(G)-U$ of vertices in $U$ are called the neighbors of $U$, denoted by $N_G(U)$. We denote a complete graph with $n$ vertices by $K_n$. A graph $G$ is said to be $k$-regular if every vertex of it has $k$ neighbors. If $G_1$ is a subgraph of $G$, denoted by $G_1\subseteq G$, then $V(G_1)\subseteq V(G)$ and $E(G_1)\subseteq E(G)$. If $G\cong H$, then $G$ is isomorphic to $H$. Let $G_1\preceq H$ denote $G_1$ to be isomorphic to a connected subgraph of $H$. We use $G[H]$ to represent the subgraph induced by $H$, which consists of the vertex set of $H$ and the edge set $\{(u, v)|u, v\in V(H), (u, v)\in E(G)\}$. Terminologies not given here can be referred to^[1].

Here is the definitions of the structure connectivity and substructure connectivity:

Definition 2.1. Let $H$ be a connected subgraph of $G$ and $F$ be a set of subgraphs of $G$ such that every element in $F$ is isomorphic to $H$. If $G-V(F)$ is disconnected, then $F$ is called an $H$-structure cut. The minimum cardinality of $H$-structure cuts is called $H$-structure connectivity of $G$, denoted by $\kappa(G; H)$.

Definition 2.2. Let $H$ be a connected subgraph of $G$ and $F^s$ be a set of subgraphs of $G$ such that every element in $F^s$ is isomorphic to connected subgraph of $H$. If $G-V(F)$ is disconnected, then $F^s$ is called an $H$-substructure cut. The minimum cardinality of $H$-substructure cuts is called $H$-substructure connectivity of $G$, denoted by $\kappa^s(G; H)$.

Obviously, $\kappa^s(G; H)\leq\kappa(G; H)$.

2.2.   The data center networks

For a positive integer $n$, we use $[n]$ and $\langle n\rangle$ to denote the sets $\{1, 2, \ldots, n\}$ and $\{0, 1, 2\ldots, n\}$, respectively. For any positive integers $k\geq0$ and $n\geq2$, we use $D_{k, n}$ to denote a $k$-dimensional $DCell$ with $n$-port switches. We use $t_{k, n}$ to denote the number of vertices in $D_{k, n}$ with $t_{0, n} = n$ and $t_{k, n} = t_{k-1, n}\times(t_{k-1, n}+1)$, where $i\in[k]$. Let $I_{0, n} = \langle n-1\rangle$ and $I_{i, n} = \langle t_{i-1, n}\rangle$ for any $i\in[k]$. Let $V_{k, n} = \{u_{k}u_{k-1}\ldots u_{0}|u_{i}\in\langle t_{i-1, n}\rangle$ and $i\in\langle k\rangle\}$, and $V^{l}_{k, n} = \{u_{k}u_{k-1}\ldots u_{l}|u_{i}\in\langle t_{i-1, n}\rangle$ and $i\in\{l, l+1, \ldots, k\}$ for any $l \in[k]\}.$ Clearly, $|V_{k, n}| = t_{k, n}$ and $|V^{l}_{k, n}| = t_{k, n}/t_{l-1, n}$. The $D_{k, n}$ is defined as follows.

Definition 2.3. The data center network $D_{k, n}$ is a graph with the vertex set $V_{k, n}$, where a vertex $u = u_{k}u_{k-1}\ldots u_{i}\ldots u_{0}$ is adjacent to a vertex $v = v_{k}v_{k-1}\ldots v_{i}\ldots v_{0}$ if and only if there is an positive integer $l$ with

(1) $u_{k}u_{k-1}\ldots u_{l} = v_{k}v_{k-1}\ldots v_{l}$,

(2) $u_{l-1}\neq v_{l-1}$,

(3) $u_{l-1} = v_{0}+\sum^{l-2}_{j = 1}(v_{j}\times t_{j-1, n})$ and $v_{l-1} = u_{0}+\sum^{l-2}_{j = 1}(u_{j}\times t_{j-1, n})+1$ with $l\geq 1$.

Lemma 2.4. ^[4] Let $D_{k, n}$ be the data center network with $k\geq0$ and $n\geq2$.

(1) $D_{0, n}$ is a complete graph with $n$ vertices labeled as $0, 1, 2, \ldots, n-1$.

(2) For $k\geq1$, $D_{k, n}$ consists of $t_{k-1, n}+1$ copies of $D_{k-1, n}$ denoted by $D^{i}_{k-1, n}$, for each $i\in\langle t_{k-1, n}\rangle$. There is one edge between $D^{i}_{k-1, n}$ and $D^{j}_{k-1, n}$ for any $i, j\in I_{k, n}$ and $i\neq j$. This implies that the outside neighbors of vertices in $D^{i}_{k-1, n}$ belong to different copies of $D^{j}_{k-1, n}$ for $j\neq i$ and $i, j\in I_{k, n}$.

(3) For any two distinct vertices $u, v$ in $D^{i}_{k-1, n}$, $N_{D^{I_{k, n}\setminus \{i\}}_{k-1, n}}(u)\cap$ $N_{D^{I_{k, n}\setminus \{i\}}_{k-1, n}}(v) = \varnothing$ and $|N_{D^{I_{k, n}\setminus \{i\}}_{k-1, n}}(u)| = 1.$

Lemma 2.5. ^[4] For any positive integers $n\geq2$ and $k\geq0$, $D_{k, n}$ has the following combinatorial properties.

(1) $D_{k, n}$ is $(n+k-1)$-regular with $t_{k, n}$ vertices and $\frac{(n+k-1)t_{k, n}}{2}$ edges.

(2) $\kappa(D_{k, n}) = \lambda(D_{k, n}) = n+k-1$.

(3) For any integer $k\geq0$, there is no cycle of length $3$ in $D_{k, 2}$ and for any integer $n\geq3$ and $k\geq0$, there exist cycles of length $3$ in $D_{k, n}$.

(4) The number of vertices in $D_{k, n}$ satisfies $t_{k, n}\geq (n+\frac{1}{2})^{2^k}-\frac{1}{2}$.

Lemma 2.6. ^[17] There exist $t_{k-1, n}$ disjoint paths (in which any two paths have no common vertices) joining $D^i_{k-1, n}$ and $D^j_{k-1, n}$ for $i, j\in I_{k, n}$, denoted by $P(D^i_{k-1, n}, D^j_{k-1, n})$.

Lemma 2.7. ^[13] For any positive integers $n\geq2$, $k\geq2$, and $0\leq g\leq n-1$, the $g$-extra connectivity of $D_{k, n}$ is $\kappa_g(D_{k, n}) = (g+1)(k-1)+n$.

The graph $D_{0, n}$ generates $D_{k, n}$ after $k$ iterations. For any vertex $u$ in $D_{0, n}$, an out neighbor is added every iteration. The graph $D_{i, n}$ consists of $t_{i-1, n}+1$ copies of $D_{i-1, n}$. Let $u^i$ be the out neighbor of $u$ in $D_{i, n}$, and $(u, u^i)$ be denoted by $i$ edge for $1\leq i\leq k$. So each vertex in some $D_{0, n}$ has $k$ neighbors and $k$ edges outside of $D_{0, n}$ in $D_{k, n}$. Several data center networks with small parameters $k$ and $n$, see Figure 2.

3.   Results of $S_m$-structure and substructure connectivity of $D_{k, n}$

Lemma 3.1. $\kappa(D_{k, n}; S_m)\leq \lceil \frac{n-1}{m+1}\rceil+k$ for $n\geq4$, $k\geq2$ and $1\leq m\leq n+k-2$.

Proof. For any $v\in V(D^i_{k-1, n})$ for $i\in I_{k, n}$. By the structure of $D_{k, n}$, we know that $v$ belongs to some $D_{0, n}$. Let the $D_{0, n}$ which $v$ is in it be $D'_{0, n}$. Since $v$ has $n-1$ neighbors in $D'_{0, n}$ and has $k$ neighbors $v^1, v^2, \ldots, v^{k}$ outside of the $D'_{0, n}$, $d(v) = n+k-1$ in $D_{k, n}$. By the construction of $D_{k, n}$, we know that $v^j$ is the out neighbor of $v$ in $D_{j, n}$ and $v^j$ in a $D_{0, n}$, denoted by $D'^j_{0, n}$ and let $v^j$ be the center vertex of an $S_m$ in $D'^j_{0, n}$ for $1\leq j\leq k$. Since there is only one edge between different copies in the same dimension, the $S_m$ in $D'^j_{0, n}$ and the $S_m$ in $D'^i_{0, n}$ have no common vertices for $1\leq i, j\leq k$ and $i\neq j$. Thus, there are $k$ $S_m$'s outside of $D'_{0, n}$ connecting to $v$. (See Figure 3.)

When $1\leq m\leq n-3$. Let $p\geq0$, $q\geq0$ be two positive integers such that $n-1 = (m+1)p+q$, where $0\leq q\leq m$. If $q = 0$, then there are $p$ $S_m$'s connecting to $v$ in $D'_{0, n}$ and $k$ $S_m$'s connecting to $v$ outside of $D'_{0, n}$. If $1\leq q\leq m$, then it means that after deleting $p$ $S_m$'s in $D'_{0, n}$ there are $q$ vertices left, except for $v$. Suppose that $w$ is one of the remaining $q$ vertices and $w$ is the center vertex of an $S_m$. Then these $q-1$ neighbors of $w$ in $D'_{0, n}$ and the $k$ neighbors outside of $D'_{0, n}$ can construct an $S_m$. Thus, there are ($\lceil \frac{n-1}{m+1}\rceil+k$) $S_m$'s connecting to $v$. The graph $D_{k, n}$ will be disconnected by deleting ($\lceil \frac{n-1}{m+1}\rceil+k$) $S_m$'s. Hence, the lemma holds.

When $n-2\leq m\leq n+k-2$, we have $\lceil \frac{n-1}{m+1}\rceil+k = 1+k$. Let $u$ be the center vertex of an $S_m$ in $D'_{0, n}$. Then $u$ has $n-2$ neighbors in $D'_{0, n}$ and $k$ neighbors outside of $D'_{0, n}$ which can construct an $S_m$ connecting to $v$. It is clearly that there are ($k+1$) $S_m$'s connecting to $v$. Thus, $D_{k, n}$ will be disconnected by deleting $(k+1)$ $S_m$'s.

Lemma 3.2. Let $F = \{T|T\cong K_1$ or $T\cong S_m, n-2\leq m\leq n \}$. Then $D_{2, n}-F$ is connected for $n\geq4$ and $|F|\leq2$.

Proof. To prove this lemma by induction $n$. Clearly, $D_{2, 4}-F$ is connected when $|F|\leq2$. Suppose that $D_{2, n-1}-F$ is connected when $|F|\leq2$ for $F = \{T|T\cong K_1$ or $T\cong S_m, n-3\leq m\leq n-1\}$. When $F = \{T|T\cong K_1\}$ and $|F|\leq2$, it is obviously that $D_{2, n}-F$ is connected. When $F = \{T|T\cong S_m, n-2\leq m\leq n\}$, it means that the center vertex of each $S_m$ in $D_{2, n}$ has at most one more neighbor deleted than the center vertex of each $S_m$ in $D_{2, n-1}$. Since by the structure of $D_{2, n-1}$ and $D_{2, n}$, for any vertex $v$ in $D_{2, n-1}$, $d(v) = n$, and for any vertex $u$ in $D_{2, n}$, $d(u) = n+1$. Thus, $D_{2, n}-F$ is connected.

Lemma 3.3. Let $F = \{T|T\cong K_1$ or $T\cong S_m, 1\leq m\leq n-3 \}$. Then $D_{2, n}-F$ is connected for $n\geq4$ and $|F|\leq \lceil \frac{n-1}{m+1}\rceil+1$.

Proof. To prove this lemma by induction $n$. When $n = 4$, we have $m = 1$, $F = \{T|T\cong K_1$ or $T\cong S_1 \}$, where $S_1\cong K_2$ and $\lceil\frac{n-1}{m+1}\rceil+1 = \lceil\frac{3}{2}\rceil+1 = 3$. It is easy to check that $D_{2, 4}-F$ is connected when $|F|\leq3$. Suppose that $D_{2, n-1}-F$ is connected when $|F|\leq \lceil \frac{n-2}{m+1}\rceil+1$ for $1\leq m\leq n-4$. It suffices to show that $D_{2, n}-F$ is connected when $|F|\leq \lceil \frac{n-1}{m+1}\rceil+1$ for $1\leq m\leq n-3$.

If $\lceil \frac{n-1}{m+1}\rceil+1 = \lceil \frac{n-2}{m+1}\rceil+1$, then the conclusion obviously holds.

Suppose that $\lceil \frac{n-1}{m+1}\rceil+1-(\lceil \frac{n-2}{m+1}\rceil+1) = 1$. When $F = \{T|T\cong K_1\}$, we have $|F|\leq \lceil \frac{n-1}{m+1}\rceil+1 = n-1+1 = n$. Since $\kappa(D_{2, n}) = n+1$, by Lemma 2.5, $D_{2, n}-F$ is connected. When $F = \{T|T\cong S_m, 1\leq m\leq n-3 \}$, by inductive hypothesis, $D_{2, n-1}-F$ is connected for $|F|\leq \lceil \frac{n-2}{m+1}\rceil+1$ and $1\leq m\leq n-4$. Since $\lceil \frac{n-1}{m+1}\rceil+1-(\lceil \frac{n-2}{m+1}\rceil+1) = 1$, it means that only more one $S_m$ is deleted in $D_{2, n}$ than in $D_{2, n-1}$. Let the center vertex of this $S_m$ be $u$.

Assume that $u$ is in $D^i_{1, n}$ for $i\in I_{2, n}$. Let $F^i = F\cap D^i_{1, n}$. By the structure of $D_{k, n}$, we know that $D_{1, n}$ is made up of $n+1$ copies of $D_{0, n}$, where $D_{0, n}\cong K_n$ and $D_{1, n-1}$ is made up of $n$ copies of $D_{0, n-1}$, where $D_{0, n-1}\cong K_{n-1}$. When $D_{1, n-1}$ goes to $D_{1, n}$, each copy of $D_{0, n-1}$ adds a vertex to $D_{0, n}$, and another copy of $D_{0, n}$ is added. In this case, $u$ is a new vertex from $D_{1, n-1}$ to $D_{1, n}$. By the structure of $D_{2, n}$, $u$ has only one out neighbor $u'\in V(D^k_{1, n})$, it is clearly that $D^k_{1, n}-F^k$ is connected, so $G[\cup_{i\neq l\in I_{1, n}}V(D^l_{1, n}-F^l)]$ is connected for $i\in I_{2, n}$. Since $D^i_{1, n}\cong D_{1, n}$, $u$ is in a $D_{0, n}$, denoted by $D'_{0, n}$. For any a vertex $v$ in $D^i_{1, n}-F^i$, if $v\notin V(D'_{0, n})$, then it is clearly that $v$ connects $G[\cup_{i\neq l\in I_{1, n}}V(D^l_{1, n}-F^l)]$. If $v\in V(D'_{0, n})$, since $D'_{0, n}\cong K_n$, then we have that $v'$ which is a neighbor of $v$ connects $G[\cup_{i\neq l\in I_{1, n}}V(D^l_{1, n}-F^l)]$. So $D_{2, n}-F$ is connected.

Assume that $u$ is in $D^i_{1, n-1}$ for $i\in I_{2, n-1}$. Let $F_i = F\cap D^i_{1, n-1}$. By the structure of $D_{2, n}$, $u$ has only one out neighbor $u'\in V(D^j_{1, n-1})$. If $D_{2, n-1}-F$ is disconnected, then $D^i_{1, n-1}-F_i$ or $D^j_{1, n-1}-F_j$ is disconnected and $G[\cup_{l\in I_{2, n-1}}V(D^l_{1, n}-F^l)]$ is connected for $i\neq j, i\neq l, j\neq l$. Without loss of generality, suppose that $D^i_{1, n-1}-F_i$ is disconnected. For any vertex $w$ of each component of $D^i_{1, n-1}-F_i$ adds a new neighbor $w'$, when $D^i_{1, n-1}$ becomes $D^i_{1, n}$. We have that $w'$ has an out neighbor $w''$ which is in $G[\cup_{l\in I_{2, n}}V(D^l_{1, n}-F^l)]$ for $i\neq j, i\neq l, j\neq l$. (See Figure 4.) It is clearly that $G[\cup_{j\neq l\in I_{1, n}}V(D^l_{1, n}-F^l)]$ is connected for $j\in I_{2, n}$.

By Lemma 2.6, there exist $t_{1, n}$ disjoint paths (in which any two paths have no common vertices) joining $D^i_{1, n}$ and $D^j_{1, n}$ for $i, j\in I_{2, n}$, then we can get that $t_{1, n}\geq (n-\frac{1}{2})^2+\frac{1}{2}$ for $n\geq4$, furthermore $t_{1, n}\geq (n+\frac{1}{2})^2+\frac{1}{2} > 3n-6\geq|V(F)|$. This implies that there is at least a path between $D^i_{1, n}$ and $D^j_{1, n}$ in $D_{2, n}-F$. So $D_{2, n}-F$ is connected when $|F|\leq \lceil \frac{n-1}{m+1}\rceil+1$.

Lemma 3.4. $\kappa^s(D_{k, n}; S_m)\geq \lceil \frac{n-1}{m+1}\rceil+k$ for $n\geq4$, $k\geq2$ and $1\leq m\leq n+k-2$.

Proof. For an positive integer $t$, let $F = \{T_j|T_j\cong K_1$ or $T_j\cong S_m, 1\leq m\leq n+k-2, 1\leq j\leq t\}$ and $|F| = t$. Let $F^i = \{T_j|T_j\cong K_1$ or $T_j\cong S_m, T_j\cap D^i_{k-1, n}, 1\leq m\leq n+k-2$, $1\leq j\leq t\}$ and $C^i$ be the set of the center vertex of $F$ in $D^i_{k-1, n}$ for $i\in I_{k, n}$. Divide it into the following two cases:

Case 1. $n-2\leq m\leq n+k-2$.

Note that $n-2\leq m\leq n+k-2$, it is clearly that $\lceil \frac{n-1}{m+1}\rceil = 1$. Thus, $\kappa^s(D_{k, n}, S_m)\geq \lceil \frac{n-1}{m+1}\rceil+k = 1+k$ for $n\geq4$ and $k\geq2$. We need to show that $D_{k, n}-F$ is connected when $|F|\leq k$. To prove it by induction on $k$. When $k = 2$, $D_{2, n}-F$ is connected by Lemma 3.2. For each $S_m$ ($n-2\leq m\leq n+k-2$) in $D_{k, n}$, there might be one more vertex than the $S_m$ ($n-2\leq m\leq n+k-3$) in $D_{k-1, n}$, but each vertex in $D_{k, n}$ has one more neighbor than the $S_m$ in $D_{k-1, n}$, so we don't have to think about the size of $S_m$ that we delete here, we think about the number of $S_m$ that we delete. Suppose that $D_{k-1, n}-F$ is connected when $|F|\leq k-1$. In the following, we prove that $D_{k, n}-F$ is connected when $|F|\leq k$ for $k\geq3$.

Case 1.1 $|C^i| = k$.

By the structure of $D_{k, n}$, each center vertex of $S_m$ in $D^i_{k-1, n}$ has at most an out neighbor in $D^j_{k-1, n}$, thus $|F^j|\leq 1$ for $i\neq j\in I_{k, n}$, so the subgraph induced by $\bigcup_{i\neq j\in I_{k, n}}V(D^j_{k-1, n}-F^j)$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It means that $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected when $|F|\leq k$.

Case 1.2 $|C^i| = k-1$.

Let $w$ be the center vertex of $S_m$ in $D^l_{k-1, n}$ for $i\neq l\in I_{k, n}$.

Suppose that $w$ has no out neighbor in $D^i_{k-1, n}$. If $w$ has an out neighbor in $D^j_{k-1, n}$ and a center vertex of $S_m$ in $D^i_{k-1, n}$ also has an out neighbor in $D^j_{k-1, n}$, then $|F^j| = 2$ for $i\neq l\neq j\in I_{k, n}$. By the induction hypothesis, $D^j_{k-1, n}$ is connected for $j\in I_{k, n}$. By Lemma 2.4(2) and Lemma 2.5(4), we can get that each copy has $t_{k-1, n}$ out edges and $t_{k-1, n}\geq (n+\frac{1}{2})^{2^{k-1}}-\frac{1}{2} > 2$ for $n\geq4$, $k\geq3$. Thus, the subgraph induced by $\bigcup_{i\neq j\in I_{k, n}}V(D^j_{k-1, n}-F^j)$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It implies that $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected.

Suppose that $w$ has an out neighbor in $D^i_{k-1, n}$. So $w$ has no out neighbor in $D^j_{k-1, n}$, it follows that $|F^j|\leq 1$ for $i\neq l\neq j\in I_{k, n}$. By induction hypothesis, $D^i_{k-1, n}$ may be disconnected but $D^j_{k-1, n}$ is connected for $i\neq j\in I_{k, n}$. So the subgraph induced by $\bigcup_{i\neq j\in I_{k, n}}V(D^j_{k-1, n}-F^j)$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It means that $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected.

Case 1.3 $|C^i|\leq k-2$.

Suppose that all center vertices of $S_m$'s which are outside of $D^i_{k-1, n}$ have an out neighbor in $D^i_{k-1, n}$. Hence, $|F^i| = k$, then $D^i_{k-1, n}-F^i$ may be disconnected. Since each vertex has only an out neighbor, we know that $D^j_{k-1, n}-F^j$ is connected for $i\neq j\in I_{k, n}$. So the subgraph induced by $\bigcup_{i\neq j\in I_{k, n}}V(D^j_{k-1, n}-F^j)$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It means that $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected.

Suppose that at least one center vertex of $S_m$ which is outside of $D^i_{k-1, n}$ has no out neighbor in $D^i_{k-1, n}$. By induction hypothesis, $D^i_{k-1, n}$ is connected for $i\in I_{k, n}$. When $|F|\leq k$, we have $|V(F)|\leq k*(n+k-2)$. By the structure of $D_{k, n}$, it has $t_{k-1}+1$ copies of $D_{k-1, n}$. By Lemma 2.5(4), we get that $t_{k-1, n}+1\geq (n+\frac{1}{2})^{2^{k-1}}+\frac{1}{2}$ and $t_{k-1, n}+1\geq (n+\frac{1}{2})^{2^{k-1}}+\frac{1}{2} > k*(n+k-2)$ when $n\geq4$, $k\geq3$. It means that there is at least a copy $D^h_{k-1, n}$ which is not deleted the vertices, so $|F^h| = 0$. By Lemma 2.6, there exist $t_{k-1, n}$ disjoint paths joining $D^h_{k-1, n}$ and $D^i_{k-1, n}$ for $i, h\in I_{k, n}$. Thus, $D_{k, n}-F$ is connected.

Case 2. $1\leq m\leq n-3$.

We prove it by induction on $k$. When $k = 2$, $D_{2, n}-F$ is connected by Lemma 3.3. Suppose that $D_{k-1, n}-F$ is connected for $|F|\leq \lceil \frac{n-1}{m+1}\rceil+k-2$. Divide it into the three subcases to prove that $D_{k, n}-F$ is connected when $|F|\leq \lceil \frac{n-1}{m+1}\rceil+k-1$ for $k\geq3$.

Case 2.1 $|C^i| = \lceil \frac{n-1}{m+1}\rceil+k-1$ for $i\in I_{k, n}$.

By the structure of $D_{k, n}$, each center vertex of $S_m$ in $D^i_{k-1, n}$ has at most an out neighbor in $D^j_{k-1, n}$, so $|F^j|\leq 1$ for $i\neq j\in I_{k, n}$, furthermore, the subgraph induced by $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It means that $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected when $|F|\leq \lceil \frac{n-1}{m+1}\rceil+k-1$ for $k\geq3$.

Case 2.2 $|C^i| = \lceil \frac{n-1}{m+1}\rceil+k-2$ for $i\in I_{k, n}$.

Let $w$ be the center vertex of $S_m$ in $D^h_{k-1, n}$ for $i\neq h\in I_{k, n}$.

Suppose that $w$ has no out neighbor in $D^i_{k-1, n}$. If $w$ has an out neighbor in $D^j_{k-1, n}$ and a center vertex of $S_m$ in $D^i_{k-1, n}$ also has an out neighbor in $D^j_{k-1, n}$, then $|F^j| = 2$ for $i\neq h\neq j\in I_{k, n}$. By induction hypothesis, $D^j_{k-1, n}$ is connected for $j\in I_{k, n}$. By Lemma 2.4(2) and Lemma 2.5(4), we can get that each copy has $t_{k-1, n}$ out edges and $t_{k-1, n}\geq (n+\frac{1}{2})^{2^{k-1}}-\frac{1}{2} > 2$ for $n\geq4$, $k\geq3$. It means that the graph induced by $\bigcup_{i\neq j\in I_{k, n}}V(D^j_{k-1, n}-F^j)$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It implies that the vertex $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected.

Suppose that $w$ has an out neighbor in $D^i_{k-1, n}$. So $w$ has no out neighbor in $D^j_{k-1, n}$, it follows that $|F^j|\leq 1$ for $i\neq h\neq j\in I_{k, n}$. By induction hypothesis, $D^i_{k-1, n}$ may be disconnected, but $D^j_{k-1, n}$ is connected for $i\neq j\in I_{k, n}$. So the subgraph induced by $\bigcup_{i\neq j\in I_{k, n}}V(D^j_{k-1, n}-F^j)$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It means that $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected.

Case 2.3 $|C^i|\leq \lceil \frac{n-1}{m+1}\rceil+k-3$ for $i\in I_{k, n}$.

Suppose that the center vertices of $S_m$'s which are outside of $D^i_{k-1, n}$ have an out neighbor in $D^i_{k-1, n}$. Hence, $|F^i| = \lceil \frac{n-1}{m+1}\rceil+k-1$, furthermore, $D^i_{k-1, n}-F^i$ may be disconnected. Since each vertex has only an out neighbor, we have that $D^j_{k-1, n}-F^j$ is connected for $i\neq j\in I_{k, n}$. So the subgraph induced by $\bigcup_{i\neq j\in I_{k, n}}V(D^j_{k-1, n}-F^j)$ is connected. For any vertex $u\in V(D^i_{k-1, n}-F^i)$, we have that $u$ has an out neighbor $u'$ in $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. By Lemma 2.4(2), we know that $u'\notin V(F)$. It means that $u$ connects $G[\cup_{i\neq j\in I_{k, n}}(D^j_{k-1, n}-F^j)]$. Thus, $D_{k, n}-F$ is connected.

Next, we consider that $|F^i|\leq\lceil \frac{n-1}{m+1}\rceil+k-2$. By induction hypothesis, $D^i_{k-1, n}$ is connected for $i\in I_{k, n}$. Hence,

By the structure of $D_{k, n}$ and Lemma 2.5(4), we can get that $t_{k-1, n}+1\geq (n+\frac{1}{2})^{2^{k-1}}+\frac{1}{2}$. It is easy to check that $t_{k-1, n}+1\geq (n+\frac{1}{2})^{2^{k-1}}+\frac{1}{2} > (n-1)*(k+1) > |V(F)|$ for $n\geq4$ and $k\geq3$. It implies that at least one copy $D^s_{k-1, n}$ is not deleted a vertex for $s\in I_{k, n}$. By Lemma 2.6, there exist $t_{k-1, n}$ disjoint paths joining $D^s_{k-1, n}$ and $D^i_{k-1, n}$ for $i, s\in I_{k, n}$, so $D_{k, n}-F$ is connected.

By Lemma 3.1 and Lemma 3.4, we obtain the following result.

Theorem 3.5. Let $n\geq4$, $k\geq2$ and $1\leq m\leq n+k-2$. Then $\kappa(D_{k, n}; S_m) = \kappa^s(D_{k, n}; S_m) = \lceil \frac{n-1}{m+1}\rceil+k$.

4.   Results of $S_{23}$-structure and substructure connectivity of $D_{k, n}$

For any vertex $u$ in $D_{k, n}$, it has $(n-1+k)$ neighbors: $(n-1)$ neighbors in a copy of $D_{0, n}$, denoted by $D'_{0, n}$ and $k$ neighbors outside of $D'_{0, n}$, denoted by $u^1, u^2, \dots, u^k$. In $D_{1, n}$, the vertex $u^1$ is called an out neighbor of $u$; in $D_{2, n}$, the vertex $u^2$ is called an out neighbor of $u$, moreover, $u$ and $u^1$ are in the same copy $D^i_{1, n}$ for $i\in I_{2, n}$. So in $D_{k, n}$, the vertex $u^k$ is called an out neighbor of $u$ and $u, u^1, u^2, \dots, u^{k-1}$ are in the same copy $D^i_{{k-1}, n}$ for $j\in I_{k, n}$. In the same dimensional copy, each vertex has only one out neighbor, so there is no edge $(u^i, u^j)$. Thus, $u^i$ and $u^j$ have no other common neighbors except for vertex $u$ for $u^i, u^j\in\{u^1, u^2, \dots, u^k\}$.

In this part, we prove the results of $S_{23}$ structure and substructure connectivity of $D_{k, n}$.

Lemma 4.1. Let $S_{23}$ be a $2$-step star with $7$ vertices. For any vertex $v$ in $D_{k, n}$, it has $k$ neighbors outside of a $D_{0, n}$, denoted by $\{v^1, v^2, \dots, v^k\}$. Let $T = \{v^1, v^2, \dots, v^k\}$. Then $|V(S_{23})|\cap|T|\leq2$.

Proof. Assume that $v\in V(D^i_{k-1, n})$ for $i\in I_{k, n}$. Let $w$ be the center vertex of the $S_{23}$ in $D^l_{k-1, n}$ for $i\neq l\in I_{k, n}$. (The case of $w$ in $D^i_{k-1, n}$ is similar to the case of $w$ in $D^l_{k-1, n}$.) Let $w^k$ be the out neighbor of $w$, furthermore, $w^1$ and $w^2$ be neighbors of $w$ in $D^l_{k-1, n}$. If $w^k$ is in $D^i_{k-1, n}$, then the $S_{23}$ has two vertices in $D^i_{k-1, n}$. Since each vertex has only one out neighbor, it is clearly that $v^k$ is not an out neighbor of $w^1$ or $w^2$. Since there is no edge $(v^i, v^j)$ for $v^i, v^j\in\{v^1, v^2, \dots, v^{k-1}\}$, we have $|V(S_{23})|\cap |T|\leq1$. If $w^k$ is in $D^j_{k-1, n}$ for $i\neq l\neq j\in I_{k, n}$, then the $S_{23}$ has two vertices in $D^j_{k-1, n}$. In this case, $v^k$ can be a neighbor of $w^k$ and the out neighbor of $w^1$ or $w^2$ can be $v^i$ for $v^i\in\{v^1, v^2, \dots, v^{k-1}\}$. (See Figure $5$.) So we have $|V(S_{23})|\cap|T|\leq2$. Next, we show that $|V(S_{23})|\cap|T|\geq3$ does not hold. It is clearly that $v^1, v^2, \dots, v^k \in V(D^i_{k-1, n})\cup V(D^j_{k-1, n})$. The vertices of the $S_{23}$ has at most $3$ out neighbors and there is only one edge between any two copies, so at most two out neighbors of an $S_{23}$ are in $D^i_{k-1, n}$ and $D^j_{k-1, n}$. Thus, $|V(S_{23})|\cap |T|\leq2$.

Lemma 4.2. Let $n\geq8$ and $k\geq3$. Then $\kappa(D_{k, n}, S_{23})\leq \lceil \frac{n-1}{7}\rceil+\frac{k}{2}$ for even $k$ and $\kappa(D_{k, n}; S_{23})\leq \lceil \frac{n-2}{7}\rceil+\frac{k+1}{2}$ for odd $k$.

Proof. For any vertex $v$ in $D^i_{k-1, n}$, let $v$ be in $D'_{0, n}$, where $D'_{0, n}\cong K_n$, then $v$ has $k$ neighbors outside of $D'_{0, n}$, denoted by $v^1, v^2, \dots, v^k$ and $n-1$ neighbors in $D'_{0, n}$.

When $k$ is even. By Lemma 4.1, an $S_{23}$ contains at most two vertices of $v^1, v^2, \dots, v^k$, so there are $\frac{k}{2}$ $S_{23}$'s connecting to $v$ outside of $D'_{0, n}$. Let $p\geq0$, $q\geq0$ be two positive integers such that $n-1 = 7p+q$, where $q\leq6$. If $q = 0$, then there are $p$ $S_{23}$'s connecting to $v$ in $D'_{0, n}$ and $\frac{k}{2}$ $S_{23}$'s connecting to $v$ outside of $D'_{0, n}$. If $1\leq q\leq6$, then there are $p$ $S_{23}$'s connecting to $v$ and $q$ neighbors of $v$ are left in $D'_{0, n}$ and $\frac{k}{2}$ $S_{23}$'s connecting to $v$ outside of $D'_{0, n}$. Here we only illustrate the case when $q = 1$, denoted by $u$, other cases are similar. In $D_{k, n}$, the vertex $u$ has at least three neighbors outside of $D'_{0, n}$, denoted by $x, y, w$, because $k\geq3$. Let $x', y', w'$ be the neighbors of $x, y, w$, respectively. Then $u, x, y, w, x', y', w'$ constitute an $S_{23}$. Hence, there are $(p+1)$ $S_{23}$'s connecting to $v$ in $D'_{0, n}$ when $1\leq q\leq6$. The graph $D_{k, n}$ will be disconnected by deleting $\lceil \frac{n-1}{7}\rceil+\frac{k}{2}$ $S_{23}$'s.

When $k$ is odd. By Lemma 4.1, there are $\frac{k-1}{2}$ $S_{23}$'s connecting to the vertex $v$ outside of $D'_{0, n}$ and $v^k$ are left in $D^j_{k-1, n}$. We construct an $S_{23}$ which contains $v^k$ and $v'$, where $v'$ is the neighbor of $v$ in $D'_{0, n}$. (See Figure $6$.) Then there are $\lceil \frac{n-2}{7}\rceil$ $S_{23}$'s connecting to $v$ in $D'_{0, n}$ and $\frac{k-1}{2}+1$ $S_{23}$'s connecting to the vertex $v$ outside of $D'_{0, n}$. The graph $D_{k, n}$ will be disconnected by deleting $(\lceil \frac{n-2}{7}\rceil+\frac{k+1}{2})$ $S_{23}$'s.

Lemma 4.3. Let $n\geq8$ and $k\geq8$. Then $\kappa^s(D_{k, n}; S_{23})\geq \lceil \frac{n-1}{7}\rceil+\frac{k}{2}$ for even $k$, and $\kappa^s(D_{k, n}; S_{23})\geq \lceil \frac{n-2}{7}\rceil+\frac{k+1}{2}$ for odd $k$.

Proof. We show that $\kappa^s(D_{k, n}, S_{23})\geq \lceil \frac{n-1}{7}\rceil+\frac{k}{2}$ when $k$ is even. Let $F = \{T|T\preceq S_{23}\}$ and $F^i = \{T_i|T_i\preceq S_{23}, T_i\cap D^i_{k-1, n}\}$ for $i\in I_{k, n}$. In the following, we prove that $D_{k, n}-F$ is connected when $|F|\leq \lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1$. To the contrary, suppose that $D_{k, n}-F$ is disconnected and $G_0$ is a smallest component of $D_{k, n}-F$.

$|V(F)| = (\lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1)*7\leq (\frac{n-1+6}{7}+\frac{k}{2}-1)*7 = \frac{7}{2}k+n-2 < 4k+n-4 = \kappa_3(D_{k, n})$.

By Lemma 2.7, we have $|V(G_0)|\leq3$, thus discussion as follows:

Case 1. $|V(G_0)| = 1$.

Set $V(G_0) = \{v\}$. Thus $N(v)\subseteq V(F)$. To make the number of subgraphs of $S_{23}$'s minimum which contain the vertices in $N(v)$, we should construct as many $S_{23}$'s as possible and each $S_{23}$ needs to contain as many vertices in $N(v)$ as possible. Since $v$ has $n-1$ neighbors in a $D_{0, n}$ which is denoted by $D'_{0, n}$ and has $k$ neighbors $v^1, v^2, \ldots, v^{k}$ outside of the $D'_{0, n}$, each $S_{23}$ contains at most seven vertices in $D'_{0, n}$ or each $S_{23}$ contains at most two vertices of $v^1, v^2, \ldots, v^{k}$ by Lemma 4.1. Then $|F|\geq \lceil \frac{n-1}{7}\rceil+\frac{k}{2} > \lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1\geq |F|$, a contradiction.

Case 2. $|V(G_0)| = 2$.

Set $V(G_0) = \{u, w\}$. Thus $N(\{u, w\})\subseteq V(F)$. Let $u$ be in a $D_{0, n}$, denoted by $D''_{0, n}$. If $w$ is in $D''_{0, n}$, then $w$ and $u$ have $(n-2)$ common neighbors in $D''_{0, n}$. The vertex $w$ has $k$ neighbors outside of $D''_{0, n}$ and $v$ also has $k$ neighbors outside of $D''_{0, n}$. Furthermore, each $S_{23}$ contains at most seven vertices in $D''_{0, n}$ or each $S_{23}$ contains at most two vertices of the neighbors outside of the $D''_{0, n}$, by Lemma 4.1. So $|F|\geq \lceil \frac{n-2}{7}\rceil+\frac{2k}{2} = \lceil \frac{n-2}{7}\rceil+k > \lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1\geq |F|$ for $n\geq8$ and $k\geq8$, a contradiction. If $w$ is neighbor of $u$ outside of $D''_{0, n}$, then $w$ and $u$ have no common neighbors. The vertex $u$ has $n-1$ neighbors in $D''_{0, n}$ and $k-1$ neighbors outside of $D''_{0, n}$ except for $w$. Furthermore, each $S_{23}$ contains at most seven vertices in $D''_{0, n}$ or each $S_{23}$ contains at most two vertices of the neighbors outside of the $D''_{0, n}$, by Lemma 4.1. (The same situation for $w$.) So $|F|\geq 2*\lceil \frac{n-1}{7}\rceil+2*\frac{k-1}{2} = 2*\lceil \frac{n-2}{7}\rceil+(k-1) > \lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1\geq |F|$ for $n\geq8$ and $k\geq8$, a contradiction.

Case 3. $|V(G_0)| = 3$.

Set $V(G_0) = \{x, y, z\}$. Thus $N(\{x, y, z\})\subseteq V(F)$. To make the number of subgraphs of $S_{23}$'s minimum which contain the vertices in $N(\{x, y, z\})$, we should construct as many $S_{23}$'s as possible and each $S_{23}$ needs to contain as many vertices in $N(\{x, y, z\})$ as possible. When $x, y$ and $z$ are in a same $D_{0, n}$, denoted by $D'''_{0, n}$, they have $(n-3)$ common neighbors in $D'''_{0, n}$ and each of $x, y, z$ has $k$ neighbors outside of $D'''_{0, n}$. Each $S_{23}$ contains at most seven vertices in $D'''_{0, n}$ or an $S_{23}$ contains at most two vertices of their neighbors outside of $D'''_{0, n}$ by Lemma 4.1. Then $|F|\geq \lceil \frac{n-3}{7}\rceil+3*\frac{k}{2} > \lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1\geq |F|$ for $n\geq8$ and $k\geq8$, a contradiction. When $x, y$ and $z$ are in two different $D_{0, n}$, without loss of generality, assume that $x$ and $y$ are in $D'''_{0, n}$ and $z$ is in another $D_{0, n}$. Then $x$ and $y$ have $(n-2)$ common neighbors, each of $x, y$ has $k$ neighbors outside of $D'''_{0, n}$. And $z$ has $(n-1)$ neighbors in a $D_{0, n}$ and $(k-1)$ neighbors outside of a $D_{0, n}$ except for $x$ or $y$. Then $|F|\geq \lceil \frac{n-2}{7}\rceil+\lceil \frac{n-1}{7}\rceil+2*\frac{k}{2}+\frac{k-1}{2} > \lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1\geq |F|$ for $n\geq8$ and $k\geq8$, a contradiction. When $x, y$ and $z$ are in three different $D_{0, n}$, each of $x, y, z$ has $(n-1)$ neighbors in a $D_{0, n}$ and $(k-1)$ neighbors outside of a $D_{0, n}$. Then $|F|\geq 3*\lceil\frac{n-1}{7}\rceil+3*\frac{k-1}{2} > \lceil \frac{n-1}{7}\rceil+\frac{k}{2}-1\geq |F|$ for $n\geq8$ and $k\geq8$, a contradiction.

The proof of $\kappa^s(D_{k, n}, S_{23})\geq \lceil \frac{n-2}{7}\rceil+\frac{k+1}{2}$ when $k$ is odd is similar to the case when $k$ is even.

By Lemma 4.2 and Lemma 4.3, we have the following result.

Theorem 4.4. Let $n\geq8$, $k\geq8$. Then $\kappa(D_{k, n}; S_{23}) = \kappa^s(D_{k, n}; S_{23}) = \lceil \frac{n-1}{7}\rceil+\frac{k}{2}$ for even $k$, and $\kappa(D_{k, n}; S_{23}) = \kappa^s(D_{k, n}; S_{23}) = \lceil \frac{n-2}{7}\rceil+\frac{k+1}{2}$ for odd $k$.

5.   Conclusions

Structure connectivity and substructure connectivity are important parameters for measuring network fault tolerance. In this paper, we obtain that $\kappa(D_{k, n}; S_m) = \kappa^s(D_{k, n}; S_m) = \lceil \frac{n-1}{m+1}\rceil+k$ for $n\geq4$, $k\geq2$ and $1\leq m\leq n+k-2$. And when $n\geq8$, $k\geq8$, we prove that $\kappa(D_{k, n}; S_{23}) = \kappa^s(D_{k, n}; S_{23}) = \lceil \frac{n-1}{7}\rceil+\frac{k}{2}$ for even $k$, and $\kappa(D_{k, n}; S_{23}) = \kappa^s(D_{k, n}; S_{23}) = \lceil \frac{n-2}{7}\rceil+\frac{k+1}{2}$ for odd $k$.

Acknowledgments

This work is supported by the Science Found of Qinghai Province (No. 2021-ZJ-703), the National Science Foundation of China (Nos.11661068, 12261074 and 12201335).

Conflict of interest

No potential conflict of interest was reported by the authors.