The $g$-extra $H$-structure connectivity and $g$-extra $H$-substructure connectivity of hypercubes

1.   Introduction

The pattern of connections between components in a parallel computer system is called the interconnection network of that system. Current massively parallel processing systems are connected by interconnection networks with tens of thousands of processors, compute nodes, storage units, etc., thus achieving spatial parallelism. As the number of processors in a parallel computer continues to increase, the overhead of communicating between processors through interconnections is also increasing. Therefore, the implementation of parallel computer system functions depends heavily on the performance of the system interconnection network.

An interconnection network is a network in which multiple processors or functional components within a computer are interconnected by switching elements according to a certain topology and control method. The topology of an interconnection network is the main structural characteristic of an interconnection network. From a graph theory perspective, the topology of an interconnection network can be represented as a graph, with the vertices of the graph representing the processors in the system, and the edges of the graph representing the communication links between the components.

Traditionally, the reliability of interconnection networks has been measured in terms of connectivity of a graph. In the late 1980s, in the study of the network reliability, it was found that there were some obvious shortcomings in measuring the reliability of interconnected networks in terms of edge connectivity and connectivity of a graph: first, both parameters are analyzed and applied with the implicit assumption that all neighbors of each node would fail at the same time. However, a network application practice shows that this is almost impossible. Second, when nodes fail simultaneously and the remaining network does not remain connected, no further consideration is given to whether each connected component still retains certain necessary properties.

Inspired by the classical connectivity defect, Harary^[13] proposed the conditional connectivity, which is the minimum number of vertices removed to make the graph disconnected and placing some requirements on the components. Among all kinds of conditional connectivities, the $g$-extra connectivity proposed by Fàbrega and Fiol ^[3,4] is one of the most studied conditional connectivity. Let $S$ be a vertex set of a graph $G$. If $S$ is called a $g$-extra cut, then $G-S$ is disconnected and each component of $G-S$ has at least $g+1$ vertices. The cardinality of a minimum $g$-extra cut of $G$, denoted by $\kappa_g(G)$, is the $g$-extra connectivity of $G$. Obviously, $\kappa_0(G) = \kappa(G)$, so the $g$-extra connectivity can be regarded as a generalization of classical connectivity and it can more accurately measure the reliability of a network. Determining the general $g$-extra connectivity of a graph is not easy work, so there are many results when $g$ is a small parameter and there are also some general results, refer to ^{[5,9,11,12,14,19,21]}. What fails in an interconnection network is often a specific structure, not just individual vertices. The concepts of the structure connectivity and the substructure connectivity were proposed by Lin et al.^[10]. Let $H$ be a connected subgraph of $G$ and $F$ be a set of subgraphs of a graph $G$ such that every element in $F$ is isomorphic to $H$ (resp. the subgraph of $H$). If $G-V(F)$ is disconnected, then $F$ is called an $H$-structure cut (resp. $H$-substructure cut). The minimum cardinality of $H$-structure cuts (resp. $H$-substructure cuts) is called the $H$-structure connectivity (resp. $H$-substructure connectivity) of $G$, denoted by $\kappa(G; H)$ (resp. $\kappa^s(G; H)$). The results of the structure connectivity and substructure connectivity of many network graphs have been studied^{[6,7,8,17,18]}.

In order to more accurately measure the reliability of a network, we combine the concepts of the $g$-extra connectivity and the structure connectivity and substructure connectivity to propose two novel kinds of connectivity: $g$-extra $H$-structure connectivity and $g$-extra $H$-substructure connectivity. The two novel connectivities not only retain each connected component property after deleting the faulty vertices, but also take into account the structure of the deleted vertices, which is a more general conditional connectivity.

In this paper, we use $G-F$ to represent the subgraph obtained from $G$ by deleting all vertices in $F$. The following are definitions of the $g$-extra $H$-structure connectivity and $g$-extra $H$-substructure connectivity.

Definition 1.1. Let $H$ be a connected subgraph of $G$ and $g$ be a nonnegative number. If $F$ is a set of subgraphs of $G$ such that every element in $F$ is isomorphic to $H$, then $F$ is called a $g$-extra $H$-structure cut satisfying that $G-F$ is disconnected and each component of $G-F$ has at least $g+1$ vertices. The $g$-extra $H$-structure connectivity of $G$, denoted by $\kappa_g(G; H)$, is defined as $\kappa_g(G; H)$ = min$\{|F||F$ is a $g$-extra $H$-structure cut of $G\}$, where $|F|$ is the number of elements in $F$.

Definition 1.2. Let $H$ be a connected subgraph of $G$ and $g$ be a nonnegative number. If $F$ is a set of subgraphs of $G$ such that every element in $F$ is isomorphic to a connected subgraph $H$, then $F$ is called a $g$-extra $H$-substructure cut satisfying that $G-F$ is disconnected and each component of $G-F$ has at least $g+1$ vertices. The $g$-extra $H$-substructure connectivity of $G$, denoted by $\kappa^s_g(G; H)$, is defined as $\kappa^s_g(G; H)$ = min$\{|F||F$ is a $g$-extra $H$-substructure cut of $G\}$, where $|F|$ is the number of elements in $F$.

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

2.   Preliminaries

2.1.   Basic notations and definitions

Table 1 gives some of the notations that will be used in this paper. For relevant concepts and notations which are not mentioned in this Table 1 below may refer to ^[1].

2.2.   The hypercube

The hypercube is the most dominant interconnection network topology used by computer systems today, for example, the famous parallel computing systems Cray T3D, Cray T3E, IBM Blue Gene, etc., are built with it as the interconnection network topology. The hypercube $Q_n$ has $n2^{n-1}$ edges and $2^n$ vertices. For every vertex $v$ in $Q_n$, it is represented as $v = x_1x_2\ldots x_n$ for $x_i\in\{0, 1\}$ and $1\leq i\leq n$. If two vertices differ in only one position, then they are adjacent. Noting that $v_i = x_1x_2\ldots \overline{x}_i \ldots x_n$ as the neighbor of $v$ with position $i$ different from $v$. Denoting $v_{i, j}$ as the vertex that position $i$ and position $j$ are different from $v$ and the other positions are the same. Similarly, $v_{1, 2, \ldots, k}$ denotes a vertex that is not identical to vertex $v$ at position from 1 to $k$, for $1\leq k\leq n$. We set $Q^i_n$ be the subgraph of $Q_n$ induced by the bit $n$ being $i$, where $i\in\{0, 1\}$. Obviously, $Q^i_n$ is isomorphic to $Q_{n-1}$ for $i\in\{0, 1\}$ (See Figure 1). Note that $Q_n$ is a bipartite graph, so there is no odd cycles in $Q_n$.

The following are some useful lemmas in this paper.

Lemma 2.1. ^[20] There is no 3-cycle in $Q_n$ and the cardinality of cycle in $Q_n$ is at least four.

Lemma 2.2. ^[15] Any two vertices in $Q_n$ ($n\geq3$) have exactly two common neighbors, if they have any.

Lemma 2.3. ^[16] Let $C$ be a subgraph of $Q_n$ with $|V(C)| = g+1$ for $n\geq4$. Then $|N_{Q_n}(C)|\geq(g+1)n-2g-(^g_2)$.

Lemma 2.4. ^[16] For $n\geq4$,

Lemma 2.5. ^[16] For $H\subseteq V(Q_n)$ and $Q_n-H$ is disconnected, if $|H|\leq 2n-2$ for $n\geq3$, then $Q_n-H$ has an isolated vertex (or an isolated edge) and a large component. Moreover, when $|H| = 2n-2$, we have that $Q_n-H$ has an isolated edge.

Lemma 2.6. Let $P_k$$(k\geq3)$ be a path with $k$ vertices in $Q_n$. For any edge $(u, v)\in E(Q_n)$ and $\{u, v\}\subseteq V(Q_n-P_k)$, $|N(\{u, v\})\cap V(P_k)|\leq \lceil\frac{2k}{3}\rceil$.

Proof. For any three consecutive vertices, denoted by $x, y$ and $z$, on a path $P_k$ in $Q_n$ with $\{(x, y), (y, z)\}\subseteq E(Q_n)$. We claim that $|N(\{u, v\})\cap \{x, y, z\}|\leq 2$. We prove this result by contradiction. Suppose that $|N(\{u, v\})\cap \{x, y, z\}| = 3$. If there exist two adjacent vertices of $x, y, z$ such that both are adjacent to either $u$ or $v$, then there is a 3-cycle, a contradiction to Lemma 2.1 (See Figure 2(a, b)). Otherwise, by symmetry, we may assume that $x$ and $z$ are adjacent only to $u$ and $y$ is adjacent only to $v$. Then, $N(u)\cap N(y) = \{x, z, v\}$, contradicting with Lemma 2.2 (See Figure 2(c)).

Lemma 2.7. Let $P_k$$(k\geq4)$ be a path with $k$ vertices in $Q_n$. For any $P_3$ in $Q_n$, denoted by $uvw$ and $\{u, v, w\}\subseteq V(Q_n-P_k)$, then $|N(\{u, v, w\})\cap V(P_k)|\leq \lceil\frac{3k}{4}\rceil$.

Proof. For any four consecutive vertices, denoted by $t, x, y, z$, on a path $P_k$ in $Q_n$ with $\{(t, x), (x, y),$ $(y, z)\}\subseteq E(Q_n)$. We claim that $|N(\{u, v, w\})\cap \{t, x, y, z\}|\leq 3$. Prove this result with a contradiction. Suppose that $|N(\{u, v, w\})\cap \{t, x, y, z\}| = 4$. By Lemma 2.6, at most two of the three consecutive vertices on a path $P_k$ are neighbors of $\{u, v\}$ and $|N(\{u, v\})\cap \{t, x, y, z\}|\leq3$. By symmetry, two cases need to be considered: (1) $u$ is adjacent to $t$ and $v$ is adjacent to $x$ and $z$; (2) $u$ is adjacent to $x$ and $z$ and $v$ is adjacent to $t$. If $|N(\{u, v, w\})\cap \{t, x, y, z\}| = 4$, then $w$ is adjacent to $y$. In Case (1), $N(v)\cap N(y) = \{x, z, w\}$, contradicting with Lemma 2.2. In Case (2), there is a 5-cycle, a contradiction (See Figure 3).

In the following section 3, we will give the main results of this paper.

3.   Main results

Lemma 3.1. $\kappa_1(Q_n; P_2)\leq n-1$ for $n\geq4$.

Proof. For any two vertices $u$ and $v$ in $Q_n$ and $(u, v)\in E(Q_n)$, without loss generality, suppose that $u = 00\cdots0$ and $v = 10\cdots0$. By the structure of $Q_n$, we know that $u_i$ and $v_i$ are adjacent for $2\leq i\leq n$. Hence, $(u_i, v_i)\in E(Q_n)$ and $u_iv_i\cong P_2$. It follows that there are $(n-1)$ ${P_2}'s$ to be adjacent to $uv$ (See Figure 4). Let $F = \{u_iv_i|2\leq i\leq n\}$. Then $|F| = n-1$ and $|V(F)| = 2n-2$. By Lemma 2.5, $Q_n-F$ has an isolated edge $(u, v)$ and a large component. Thus, $\kappa_1(Q_n; P_2)\leq n-1$.

Lemma 3.2. $\kappa^s_1(Q_n; P_2)\geq n-1$ for $n\geq4$.

Proof. Let $F$ be a $1$-extra $P_2$-substructure cut. Then the elements in $F$ are either isolated vertices or ${P_2}'s$. It suffices to show that $Q_n-F$ is connected when $|F|\leq n-2$. This lemma is pvoved by contradiction. Suppose that $Q_n-F$ is disconnected and $C$ is the smallest component of $Q_n-F$. Since $F$ is a $1$-extra $P_2$-substructure cut, $|V(C)|\geq2$, furthermore,

$|V(F)|\leq2(n-2) = 2n-4 < 2n-2 = \kappa_1(Q_n)$, a contradiction.

Thus, we have $|F|\geq n-1$. This proof is complete. □

By Lemma 3.1 and Lemma 3.2, we can easily obtain the following theorem.

Theorem 3.3. $\kappa_1(Q_n; P_2) = \kappa^s_1(Q_n; P_2) = n-1$ for $n\geq3$.

The following will prove the result when $3\leq k\leq 3n-4$.

Lemma 3.4. Let $m$, $n$ and $k$ be positive integers and $n\geq5$, $3\leq k\leq 3n-4$.

Proof. For any two vertices $u$ and $v$ in $Q_n$ and $(u, v)\in E(Q_n)$, without loss generality, suppose that $u = 00\cdots0$ and $v = 10\cdots0$. By the structure of $Q_n$, we know that $u_i$ and $v_i$ are adjacent for $2\leq i\leq n$. Furthermore, the vertex $v_{j, j+1}$(resp. $u_{j, j+1}$) is a common neighbor of $v_j$(resp. $u_j$) and $v_{j+1}$(resp. $u_{j+1}$) for $2\leq j\leq n-1$. It follows that $(u_j, v_j)\in E(Q_n)$, $(v_j, v_{j, j+1})\in E(Q_n)$(resp. $(u_j, u_{j, j+1})\in E(Q_n)$) and $(v_{j, j+1}, v_{j+1})\in E(Q_n)$(resp.$(u_{j, j+1}, u_{j+1})\in E(Q_n)$) (See Figure 5). In the following, we find a path formed a cut set $F$ and every element in $F$ is isomorphic to $P_k$ such that $Q_n-F$ is disconnected and the smallest component has at least two vertices. The discussion is divided into three cases:

Case 1. $k = 3m$.

Let $3n-4 = k\cdot q+r$ where $q$ and $r$ are nonnegative integers with $0\leq r < k$. When $k = 3m$, we have that $3n-4$ is not divisible by $k$, so $r\neq0$. In the following proof, we assume that $q$ is odd and the proof that $q$ is even is similar.

Case 1.1 $m$ is odd.

When $m$ is odd, we can construct the following set of path cuts where each element is isomorphic to $P_k$:

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots u_{\frac{k+3}{3}}v_{\frac{k+3}{3}}v_{\frac{k+3}{3}, \frac{k+6}{3}}$,

$P^2_k = v_{\frac{k+6}{3}}u_{\frac{k+6}{3}}u_{\frac{k+6}{3}, \frac{k+9}{3}}\cdots\cdots v_{\frac{2k+3}{3}}v_{\frac{2k+3}{3}}u_{\frac{2k+3}{3}, \frac{2k+6}{3}}$,

$\vdots$

$P^q_k = u_{\frac{(q-1)k+6}{3}}v_{\frac{(q-1)k+6}{3}}v_{\frac{(q-1)k+6}{3}, \frac{(q-1)k+9}{3}}\cdots\cdots u_{\frac{qk+3}{3}}v_{\frac{qk+3}{3}}v_{\frac{qk+3}{3}, \frac{qk+6}{3}}$,

$P^{q+1}_k = v_{\frac{qk+6}{3}}\cdots v_nu_nu_{n, 2}u_{n, 2, 3}\cdots u_{n, 2, 3, \cdots(k(q+1)-3n+4)}$.

Case 1.2 $m$ is even.

When $m$ is even, we can construct the following set of path cuts where each element is isomorphic to $P_k$:

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots v_{\frac{k+3}{3}}u_{\frac{k+3}{3}}u_{\frac{k+3}{3}, \frac{k+6}{3}}$,

$P^2_k = u_{\frac{k+6}{3}}v_{\frac{k+6}{3}}v_{\frac{k+6}{3}, \frac{k+9}{3}}\cdots\cdots u_{\frac{2k+3}{3}}u_{\frac{2k+3}{3}}v_{\frac{2k+3}{3}, \frac{2k+6}{3}}$,

$\vdots$

$P^q_k = v_{\frac{(q-1)k+6}{3}}u_{\frac{(q-1)k+6}{3}}u_{\frac{(q-1)k+6}{3}, \frac{(q-1)k+9}{3}}\cdots\cdots v_{\frac{qk+3}{3}}u_{\frac{qk+3}{3}}u_{\frac{qk+3}{3}, \frac{qk+6}{3}}$,

$P^{q+1}_k = u_{\frac{qk+6}{3}}\cdots u_nv_nv_{n, 2}v_{n, 2, 3}\cdots v_{n, 2, 3, \cdots(k(q+1)-3n+4)}$.

In Case 1, whether $m$ is odd or even, we can construct a set $F = \{P^1_k, P^2_k, \cdots, P^{q+1}_k\}$ such that $Q_n-F$ is disconnected because $\{(u, v)\}$ is a component of $Q_n-F$. In this case, $q+1 = \lceil\frac{3n-4}{k}\rceil$.

Case 2. $k = 3m+1$.

Let $3n-4-\lfloor\frac{3n-4}{2k}\rfloor = k\cdot q+r$ where $q$ and $r$ are nonnegative integers with $0\leq r < k$.

Case 2.1 $m$ is odd.

When $m$ is odd, we can construct the following set of path cuts where each element is isomorphic to $P_k$:

Case 2.1.1 $r = 0$.

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots v_{\frac{k+2}{3}}v_{\frac{k+2}{3}, \frac{k+5}{3}}v_{\frac{k+5}{3}}$,

$P^2_k = u_{\frac{k+5}{3}}u_{\frac{k+5}{3}, \frac{k+6}{3}}u_{\frac{k+6}{3}}\cdots\cdots u_{\frac{2k+1}{3}, \frac{2k+4}{3}}u_{\frac{2k+4}{3}}v_{\frac{2k+4}{3}}$,

$P^3_k = v_{\frac{2k+7}{3}}u_{\frac{2k+7}{3}}u_{\frac{2k+7}{3}, \frac{2k+10}{3}}\cdots\cdots u_{\frac{3k+3}{3}}u_{\frac{3k+3}{3}, \frac{3k+6}{3}}u_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = v_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots v_{(n-1), n}v_nu_n$. (or $P^q_k = u_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots u_{(n-1), n}u_nv_n$.)

Case 2.1.2 $r\neq0$.

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots v_{\frac{k+2}{3}}v_{\frac{k+2}{3}, \frac{k+5}{3}}v_{\frac{k+5}{3}}$,

$P^2_k = u_{\frac{k+5}{3}}u_{\frac{k+5}{3}, \frac{k+6}{3}}u_{\frac{k+6}{3}}\cdots\cdots u_{\frac{2k+1}{3}, \frac{2k+4}{3}}u_{\frac{2k+4}{3}}v_{\frac{2k+4}{3}}$,

$P^3_k = v_{\frac{2k+7}{3}}u_{\frac{2k+7}{3}}u_{\frac{2k+7}{3}, \frac{2k+10}{3}}\cdots\cdots u_{\frac{3k+3}{3}}u_{\frac{3k+3}{3}, \frac{3k+6}{3}}u_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = v_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots u_{\frac{qk+2q}{3}}$, (or $P^q_k = u_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots v_{\frac{qk+2q}{3}}$, )

$P^{q+1}_k = v_{\frac{qk+2q}{3}}\cdots\cdots u_nv_nv_{n, 2}\cdots\cdots v_{n, 2, \cdots (q+1)k-3n+2q-1}$.

(or $P^{q+1}_k = u_{\frac{qk+2q}{3}}\cdots\cdots v_nu_nu_{n, 2}\cdots\cdots u_{n, 2, \cdots (q+1)k-3n+2q-1}$.)

Case 2.2 $m$ is even.

When $m$ is even, we can construct the following set of path cuts where each element is isomorphic to $P_k$:

Case 2.2.1 $r = 0$.

$P^1_k = v_2u_2u_{2, 3}\cdots\cdots u_{\frac{k+2}{3}}u_{\frac{k+2}{3}, \frac{k+5}{3}}u_{\frac{k+5}{3}}$,

$P^2_k = v_{\frac{k+5}{3}}v_{\frac{k+5}{3}, \frac{k+6}{3}}v_{\frac{k+6}{3}}\cdots\cdots v_{\frac{2k+1}{3}, \frac{2k+4}{3}}v_{\frac{2k+4}{3}}u_{\frac{2k+4}{3}}$,

$P^3_k = u_{\frac{2k+7}{3}}v_{\frac{2k+7}{3}}v_{\frac{2k+7}{3}, \frac{2k+10}{3}}\cdots\cdots v_{\frac{3k+3}{3}}v_{\frac{3k+3}{3}, \frac{3k+6}{3}}v_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = u_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots u_{(n-1), n}u_nv_n$. (or $P^q_k = v_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots v_{(n-1), n}v_nu_n$.)

Case 2.2.2 $r\neq0$.

$P^1_k = v_2u_2u_{2, 3}\cdots\cdots u_{\frac{k+2}{3}}u_{\frac{k+2}{3}, \frac{k+5}{3}}u_{\frac{k+5}{3}}$,

$P^2_k = v_{\frac{k+5}{3}}v_{\frac{k+5}{3}, \frac{k+6}{3}}v_{\frac{k+6}{3}}\cdots\cdots v_{\frac{2k+1}{3}, \frac{2k+4}{3}}v_{\frac{2k+4}{3}}u_{\frac{2k+4}{3}}$,

$P^3_k = u_{\frac{2k+7}{3}}v_{\frac{2k+7}{3}}v_{\frac{2k+7}{3}, \frac{2k+10}{3}}\cdots\cdots v_{\frac{3k+3}{3}}v_{\frac{3k+3}{3}, \frac{3k+6}{3}}v_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = u_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots v_{\frac{qk+2q}{3}}$, (or $P^q_k = v_{\frac{(q-1)k+2q+1}{3}}\cdots\cdots u_{\frac{qk+2q}{3}}$, )

$P^{q+1}_k = u_{\frac{qk+2q}{3}}\cdots\cdots v_nu_nu_{n, 2}\cdots\cdots u_{n, 2, \cdots (q+1)k-3n+2q-1}$.

(or $P^{q+1}_k = v_{\frac{qk+2q}{3}}\cdots\cdots u_nv_nv_{n, 2}\cdots\cdots v_{n, 2, \cdots (q+1)k-3n+2q-1}$.)

In Case 2, when $m$ is odd or even and $r = 0$, we construct a set $F = \{P^1_k, P^2_k, \cdots, P^{q}_k\}$ with $q$ elements; when $m$ is odd or even and $r\neq0$, we construct a set $F = \{P^1_k, P^2_k, \cdots, P^{q}_k, P^{q+1}_k\}$ with $q+1$ elements. Then $Q_n-F$ is disconnected since $\{(u, v)\}$ is a component of $Q_n-F$. In this case, when $r = 0$, $q = \lceil\frac{3n-4-\lfloor\frac{3n-4}{2k}\rfloor}{k}\rceil$; when $r\neq0$, $q+1 = \lceil\frac{3n-4-\lfloor\frac{3n-4}{2k}\rfloor}{k}\rceil$.

Case 3. $k = 3m+2$.

Let $3n-4-\lfloor\frac{3n-4}{k}\rfloor = k\cdot q+r$ where $q$ and $r$ are nonnegative integers with $0\leq r < k$.

Case 3.1 $m$ is odd.

When $m$ is odd, we can construct the following set of path cuts where each element is isomorphic to $P_k$:

Case 3.1.1 $r = 0$.

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots u_{\frac{k+4}{3}}$, $P^2_k = u_{\frac{k+7}{3}}\cdots\cdots u_{\frac{2k+5}{3}}$, $P^3_k = u_{\frac{2k+8}{3}}\cdots\cdots u_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = u_{\frac{(q-1)k+5+q}{3}}\cdots\cdots v_nu_n$.

Case 3.1.2 $r\neq0$.

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots u_{\frac{k+4}{3}}$, $P^2_k = u_{\frac{k+7}{3}}\cdots\cdots u_{\frac{2k+5}{3}}$, $P^3_k = u_{\frac{2k+8}{3}}\cdots\cdots u_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = u_{\frac{(q-1)k+5+q}{3}}\cdots\cdots u_{\frac{qk+q+3}{3}}$,

$P^{q+1}_k = u_{\frac{qk+6+q}{3}}\cdots\cdots v_nu_nu_{n, 2}\cdots\cdots u_{n, 2, \cdots(q+1)k-3n+q+4}$.

Case 3.2 $m$ is even.

In the following proof, we assume that $q$ is odd and the proof that $q$ is even is similar. When $m$ is even, we can construct the following set of path cuts where each element is isomorphic to $P_k$:

Case 3.2.1 $r = 0$.

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots v_{\frac{k+4}{3}}$, $P^2_k = v_{\frac{k+7}{3}}\cdots\cdots u_{\frac{2k+5}{3}}$, $P^3_k = u_{\frac{2k+8}{3}}\cdots\cdots v_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = u_{\frac{(q-1)k+5+q}{3}}\cdots\cdots u_nv_n$.

Case 3.2.2 $r\neq0$.

$P^1_k = u_2v_2v_{2, 3}\cdots\cdots v_{\frac{k+4}{3}}$, $P^2_k = v_{\frac{k+7}{3}}\cdots\cdots u_{\frac{2k+5}{3}}$, $P^3_k = u_{\frac{2k+8}{3}}\cdots\cdots v_{\frac{3k+6}{3}}$,

$\vdots$

$P^q_k = u_{\frac{(q-1)k+5+q}{3}}\cdots\cdots v_{\frac{kq+q+3}{3}}$,

$P^{q+1}_k = v_{\frac{(k+1)q+6}{3}}\cdots\cdots v_nu_nu_{n, 2}\cdots\cdots u_{n, 2, \cdots (q+1)k-3n+q+4}$.

In Case 3, when $m$ is odd or even and $r = 0$, we construct a set $F = \{P^1_k, P^2_k, \cdots, P^{q}_k\}$ with $q$ elements; when $m$ is odd or even and $r\neq0$, we construct a set $F = \{P^1_k, P^2_k, \cdots, P^{q}_k, P^{q+1}_k\}$ with $q+1$ elements. Then $Q_n-F$ is disconnected since $\{(u, v)\}$ is a component of $Q_n-F$. In this case, when $r = 0$, $q = \lceil\frac{3n-4-\lfloor\frac{3n-4}{k}\rfloor}{k}\rceil$; when $r\neq0$, $q+1 = \lceil\frac{3n-4-\lfloor\frac{3n-4}{k}\rfloor}{k}\rceil$. □

Lemma 3.5. Let $m$, $n$ and $k$ be positive integers and $n\geq5$.

Proof. Let $F = \{P_i^{j_i}|1\leq j_i\leq n_i, 1\leq i\leq k\}$ be a $1$-extra $P_k$-substructure cut, and such that each element $P_i^{j_i}$ is isomorphic to $P_i$, where $n_i$ indicates the number of $p_i$.

Case 1. $k = 3m$.

In this case, it suffices to prove that if $|F|\leq \lceil\frac{3n-4}{k}\rceil-1$, then $Q_n-F$ is connected. This proof is by contradiction. Assume that $Q_n-F$ is disconnected, then

Since $F$ is a $1$-extra $P_k$-substructure cut, the smallest component $S$ of $Q_n-F$ with $|V(S)|\geq2$. Hence, it follows that $|V(S)| = 2$. Let $V(S) = \{u, v\}$, and $(u, v)\in E(Q_n)$. By Lemma 2.6, we have

a contradiction.

Case 2. $k = 3m+1$.

In this case, it suffices to prove that if $|F|\leq \lceil\frac{3n-4-\lfloor\frac{3n-4}{2k}\rfloor}{k}\rceil-1$, then $Q_n-F$ is connected. This proof is by contradiction. Assume that $Q_n-F$ is disconnected, then

Since $F$ is a $1$-extra $P_k$-substructure cut, the smallest component $S$ of $Q_n-F$ with $|V(S)|\geq2$. Hence, divided into two subcases.

Case 2.1. $|V(S)| = 2$.

Let $V(S) = \{u, v\}$, and $(u, v)\in E(Q_n)$. By Lemma 2.6, we have

a contradiction.

Case 2.2. $|V(S)| = 3$.

Let $V(S) = \{u, v, w\}$. There is no 3-cycle in $Q_n$, so $G[S]$ is a $P_3$. By Lemma 2.7, we have

a contradiction.

Case 3. $k = 3m+2$.

In this case, it suffices to prove that if $|F|\leq (\lceil\frac{3n-4-\lfloor\frac{3n-4}{k}\rfloor}{k}\rceil-1)$, then $Q_n-F$ is connected. This proof is by contradiction. Assume that $Q_n-F$ is disconnected, then

Since $F$ is a $1$-extra $P_k$-substructure cut, the smallest component $S$ of $Q_n-F$ with $|V(S)|\geq2$. Hence, divided into two subcases.

Case 3.1. $|V(S)| = 2$.

Let $V(S) = \{u, v\}$, and $(u, v)\in E(Q_n)$. By Lemma 2.6, we have

a contradiction.

Case 3.2. $|V(S)| = 3$.

Let $V(S) = \{u, v, w\}$. There is no 3-cycle in $Q_n$, so $G[S]$ is a $P_3$. By Lemma 2.7, we have

a contradiction. □

By Lemma 3.4 and Lemma 3.5, we can easily obtain the following theorem.

Theorem 3.6. Let $m$, $n$ and $k$ be positive integers and $n\geq4$.

4.   Comparative analysis

In this section, we do two sets of comparison to compare the structure connectivity results of the hypercube with the $1$-extra structure connectivity results of the hypercube. In ^[2], the authors determined the structure connectivity and substructure connectivity of the hypercube: Let $3\leq k\leq n$. Then $\kappa(Q_n, P_k) = \kappa^s(Q_n, P_k) = \lceil\frac{2n}{k+1}\rceil$ if $k$ is odd and $\kappa(Q_n, P_k) = \kappa^s(Q_n, P_k) = \lceil\frac{2n}{k}\rceil$ if $k$ is even. The value of the structure connectivity of the hypercube is equal to the value of the substructure connectivity and the value of the $1$-extra-structure connectivity of the hypercube is equal to the value of the $1$-extra substructure connectivity, here we compare only the structure connectivity of the hypercube with the $1$-extra structure connectivity. In the first set of comparisons, we obtain the results for the number of ${P_k}'s$ when the dimension of the hypercube is $30$ and the length of the ${P_k}'s$ ranges from $4$ to $25$. In Figure $6(a)$, it is clear that the results for $1$-extra structure connectivity are better than the results for structure connectivity. In comparison $2$, we obtain the results for the number of ${P_k}'s$ when the hypercube has dimension $n = \{10, 15, 20, 25\}$ and the length of the ${P_k}'s$ goes from $4$ to $10$. From the comparative results (Figure $6(b)$), it is seen that the $1$-extra structure connectivity is better than the structure connectivity when the dimensions $n$ is the same and the lengths of the ${P_k}'s$ are the same.

5.   Conclusions

In this paper, we propose two new parameters for measuring the network reliability: $g$-extra $H$-structure connectivity and $g$-extra $H$-substructure connectivity, and obtain some results for $Q_n$:

The experiments show that our results are better than those of structure connectivity and substructure connectivity. Therefore, the proposed two new parameters are meaningful. One can further consider the results for the hypercube when $g$ is larger. Of course, the results of some other well-known networks can be considered.

Use of AI tools declaration

The authors declare they have not used artificial intelligence (AI) tools in the creation of this article.

Acknowledgments

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

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.