Two kinds of conditional connectivity of hypercubes

Abstract

A subset $F\subseteq V(G)$ is called an h-extra r-component cut of G if G – F is disconnected and there are at least r components, each component has at least h + 1 vertices. The cardinality of a minimum h-extra r-component cut of G, denoted by $c{\kappa }_r^h(G),$ is the h-extra r-component connectivity of G. In this paper, we introduce a novel connectivity called the g-good r-component connectivity. For $F\subseteq V(G),$ if G – F is disconnected and there are at least r components and each vertex $v\in G-F$ has at least g neighbors, then F is called a g-good r-component cut of G; the g-good r-component connectivity of G, denoted by $c{\kappa }_{g,r}(G),$ is the minimum cardinality of a g-good r-component cut of G. In this work, we prove that $c{\kappa }_3^2(Q_n)=6n-20$ for $n\ge 9$ and $c{\kappa }_{2,3}(Q_n)=8n-24$ for $n\ge 11,$ where Q_n is n-dimension hypercube.

Keywords:

• h-extra r-component connectivity
• g-good r-component connectivity
• hypercube

1. Introduction

The topological structure of a computer interconnection network can be represented by a graph, where vertices represent processors and edges represent communication links between processors. To evaluate the reliability and fault tolerance of a network in communication, many related concepts and graph parameters have been put forward. The connectivity of graph is an important parameter reflecting the strength between two nodes in an interconnection network. The traditional connectivity of a graph is the minimum number of vertices whose removal leaves the remaining graph disconnected or trivial. Note that, in the event of a random node failure, it is very unlikely that all of the nodes adjacent to a single node fail simultaneously. Thus, the traditional connectivity has certain limitations and underestimates the resilience of the network. To measure the fault tolerance of an interconnection network more accurately, Harary [8] introduced the concept of the conditional connectivity by placing some requirements on the components of G – F for $F\subseteq V(G).$

Here are some of the most studied conditional connectivity: g-good neighbor connectivity, h-extra connectivity and r-component connectivity. For a faulty set $F\subseteq V(G),$ if F is called a g-good neighbor cut of G, then G – F is disconnected and each vertex $v\in G-F$ has at least g neighbors. The minimum cardinality of g-good neighbor cuts is said to be the g-good neighbor connectivity of G, denoted by ${\kappa }_g(G).$ The relevant results of the g-good neighbor connectivity can be referred to [11, 12, 14, 16, 19]. It was stated in [15] that introduced the concept of the g-extra connectivity, and Fàbrega and Fiol [4, 5] gave a result regarding this concept. An h-extra cut of G is a set of vertices whose deletion results in G – F is disconnected and each remaining component has more than h vertices. The h-extra connectivity of a graph G, denoted by κ^h, is the minimum cardinality of h-extra cuts of G. Recent results of the h-extra connectivity can be referred to [6, 7, 13, 23, 26]. Let G be a non-complete graph and r be a positive integer. A r-component cut of G is a set of vertices whose deletion results in at least r components. The r-component connectivity $c{\kappa }_r(G)$ of a graph G is the cardinality of the smallest r-component cut of G. For more research on the r-component connectivity, we refer to [2, 3, 9, 17, 20, 24].

The above mentioned conditional connectivity is only a condition that restricts the components of G – F. In some cases, we need to have various restrictions on the components of G – F. Recently, Li et al. [10] introduced the h-extra r-component connectivity, and the authors prove that $c{\kappa }_3^1(Q_n)=4n-8$ for $n\ge 7$ and $c{\kappa }_4^1(Q_n)=6n-18$ for $n\ge 9.$ For two integers $r\ge 2$ and $h\ge 0,$ a subset $F\subseteq V$ is called an h-extra r-component cut of G if there are at least r connected components in G – F and each component has at least h + 1 vertices. The minimum cardinality of h-extra r-component cuts of G, if exists, is the h-extra r-component connectivity of G, denoted by $c{\kappa }_r^h(G).$ At present, there are few results on the h-extra r-component connectivity.

In this paper, we give the concept of the g-good r-component connectivity.

Definition 1.1.

Let G be a connected graph, for $F\subseteq V(G),$ if G – F is disconnected and there are at last r components and each vertex $v\in G-F$ has at least g neighbors, then F is called a g-good r-component cut of G. The g-good r-component connectivity of G, denoted by $c{\kappa }_{g,r}(G),$ is the minimum cardinality of g-good r-component cuts of G.

In this work, we prove that $c{\kappa }_3^2(Q_n)=6n-20$ for $n\ge 9$ and $c{\kappa }_{2,3}(Q_n)=8n-24$ for $n\ge 11,$ where Q_n is n-dimension hypercube.

2. Preliminaries

Hypercube is a very well-known and fundamental computer network model. An n-dimension hypercube Q_n has $2^n$ vertices and $n{2}^{n-1}$ edges. Each vertex in Q_n is represented as an n-bit binary ({0, 1}) string and two vertices are adjacent if and only if they differ exactly in one position. We set $Q_{n-1}^i$ be the subgraph of Q_n induced by the bit n being i, where i = 0, 1. Obviously, $Q_{n-1}^i$ is isomorphic to $Q_{n-1}$ for i = 0, 1. For each vertex in $Q_{n-1}^0$(respectively, $Q_{n-1}^1$), there is a neighbor in $Q_{n-1}^1$(respectively, $Q_{n-1}^0$), which is called the outer neighbor. Note that Q_n is a bipartite graph, so there is no odd cycles in Q_n. See Figure 1.

Figure 1. Q_n for n = 1, 2, 3.

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. For an integer $n\ge 1,$ the path P_n is a graph of order n and size n – 1 whose vertices can be labeled by $v_1{v}_2\dots v_n.$ For an integer $n\ge 3,$ the cycle C_n is a graph of order n and size n which can be represented by $v_1{v}_2\dots v_n{v}_1.$ The degree of vertex u in graph G is the number of neighbors, denoted by d(v). 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).$ Terminologies not given here can be referred to [1].

Here are some lemmas that will be used in this paper.

Lemma 2.1

[18, 22]. For any integer $1\le t\le n+1$, the minimum number of vertices adjacent to t vertices in Q_n is $p_n(t)=-\frac{t^2}{2}+(n-\frac{1}{2})+1$. For any integer $n+2\le t\le 2n$, the minimum number of vertices adjacent to t vertices in Q_n is $q_n(t)=-\frac{t^2}{2}+(2n-\frac{3}{2})-n^2+2.$

Lemma 2.2

[25]. If $\left|F\right|<3n-5$ for $n\ge 4$, then $Q_n-F$ is either connected or disconnected with a large connected component and remaining small components containing at most two vertices in total.

Lemma 2.3

[25]. If $\left|F\right|<5n-14$ for $n\ge 4$, then $Q_n-F$ is either connected or disconnected with a large connected component and remaining small components containing at most four vertices in total.

Lemma 2.4

[21]. For $n\ge 5$ and any $T\subseteq V(Q_n)$, if $\left|T\right|\ge 2n$ and $|V(Q_n)-(T\cup N_{Q_n}(T))|\ge \left|T\right|$, then $|N_{Q_n}(T)|\ge q_n(2n)$, where $q_n(2n)$ is as defined in Lemma 2.1.

Lemma 2.5.

Let C_a and C_b be cycles with length 4 in Q_n. If $|N_{Q_n}(V(C_a))\cap V(C_b)|=\varnothing$ and $|N_{Q_n}(V(C_a))\cap V(C_b)|=\varnothing$, then $|N_{Q_n}(V(C_a))\cap N_{Q_n}(V(C_b))|\le 8.$

Proof.

Let $C_a=x_1{x}_2{x}_3{x}_4{x}_1$ and $C_b=y_1{y}_2{y}_3{y}_4{y}_1.$ By the structure of Q_n, for any two vertices x and y have either two common neighbors or no common neighbors. If x₁ and y₁ have two common neighbors, then x₁ and y₂ or y₄ have no common neighbor, otherwise, there is a cycle with length 5. Moreover, x₁ and y₃ also have no common neighbor, otherwise, there is a cycle with length 7. Similarly to x_i and y_i for $2\le i\le 4.$ So $|N_{Q_n}(V(C_a))\cap N_{Q_n}(V(C_b))|\le 8.$ □

Lemma 2.6.

For $n\ge 9$ and $1\le i\le 3,v_i,u_i\in V(Q_n)$. Let $P{\prime }_3=v_1{v}_2{v}_3$ and $P\prime {\prime }_3=u_1{u}_2{u}_3$. If $|N_{Q_n}(V(P{\prime }_3))\cap V(P\prime {\prime }_3)|=\varnothing$ and $|N_{Q_n}(V(P\prime {\prime }_3))\cap V(P{\prime }_3)|=\varnothing$, then $\left|N_{Q_n}\right\{v_1,v_2,v_3,u_1,u_2,u_3\left\}\right|\ge 6n-20.$

Proof.

Since Q_n has no odd cycle, adjacent vertices have no common neighbor. By the structure of Q_n, for any two vertices u and v, they have either two common neighbors or no common neighbor. Since v₂(respectively, u₂) is a common neighbor of v₁ and v₃(respectively, u₁ and u₃), it follows that v₁ and v₃(respectively, u₁ and u₃) have another common neighbor. Considering the following cases:

Case 1. u₁ and v₁ have two common neighbors.

Since u₁ and v₁ have two common neighbors, we know that u₁ have at most two common neighbors with v₃ and u₁, respectively. u₁ and v₂ have no common neighbor, otherwise, there is a cycle with length 5. Moreover, u₂ has no common neighbor with v₁ and v₃, otherwise, there is a cycle with length 5, and u₂ have at most two common neighbors with v₂. Similarly, u₃ have at most two common neighbors with v₁ and v₃, respectively. And u₃ have no common neighbor with v₂, otherwise, there is a cycle with length 5. By the above discussion, we can get the path $P{\prime }_3$ and $P\prime {\prime }_3$ have at most 10 common neighbors. Thus $\left|N_{Q_n}\right\{v_1,v_2,v_3,u_1,u_2,u_3\left\}\right|\ge 4(n-1)+2(n-2)-2\times 1-10=6n-20.$

Case 2. u₁ and v₂ have two common neighbors.

If u₁ and v₂ have two common neighbors, then u₁ have no common neighbor with v₁ and v₃, otherwise, there is a cycle with length 5. Vertex u₂ have at most two common neighbors with v₁, then u₂ have no common neighbor with v₂, otherwise, there is a cycle with length 5. Moreover, u₂ have at most two common neighbors with v₃. Vertex u₃ have no common neighbor with v₁ and v₃, otherwise, there is a cycle with length 7. And u₃ have at most two common neighbors with v₂. After the above discussion, we can get the path $P{\prime }_3$ and $P\prime {\prime }_3$ have at most 8 common neighbors. Thus $\left|N_{Q_n}\right\{v_1,v_2,v_3,u_1,u_2,u_3\left\}\right|\ge 4(n-1)+2(n-2)-2\times 1-8=6n-18.$

Case 3. u₁ and v₃ have two common neighbors.

The proof of this case is the same as the proof of Case 1.

Case 4. u₂ and v₁ or u₂ and v₃ have two common neighbors.

The proof for this case is the same as the proof for the Case 2.

Case 5. u₂ and v₂ have two common neighbors.

Since u₂ and v₂ have two common neighbors, we have u₂ and v₁ or u₂ and v₃ have no common neighbor, otherwise, there is a cycle with length 5. After a simple check, u₁ have at most two common neighbors with v₁ and v₃. Similarly, u₃ have at most two common neighbors with v₃ and v₁. Thus $\left|N_{Q_n}\right\{v_1,v_2,v_3,u_1,u_2,u_3\left\}\right|\ge 4(n-1)+2(n-2)-2\times 1-5\times 2=6n-20.$

Case 6. u₃ and v₁ or u₃ and v₂ or u₃ and v₃ have two common neighbors.

The proof of this case is the same as the proof of Case 1, Case 2 and Case 3, respectively. □

3. g-good r-component connectivity

In this section, we will show the 2-good 3-component connectivity of hypercubes.

Lemma 3.1.

Let Q_n be an n-dimension hypercube. Then $c{\kappa }_{2,3}(Q_n)\le 8n-24$ for $n\ge 11.$

Proof.

Let $C{\prime }_4=u_1{u}_2{u}_3{u}_4{u}_1$ and $C\prime {\prime }_4=v_1{v}_2{v}_3{v}_4{v}_1$ be cycles in Q_n. Without loss generality, suppose that $u_1=000010,\dots ,0,$ $u_2=000000,\dots ,0,u_3=000100,\dots ,0,u_4=000110,\dots ,0,$ and $v_1=011010,\dots ,0,v_2=011000,\dots ,0,$ $v_3=011100,\dots ,0,v_4=011110,\dots ,0,$ u_i and v_i have two common neighbors for $1\le i\le 4.$ We set $F=N_{Q_n}(V(C{\prime }_4))\cup N_{Q_n}(V(C\prime {\prime }_4)),$ then $\left|F\right|=8(n-2)-4\times 2=8n-24,$ see Figure 2. There are at least three components in $Q_n-F.$ For any vertex v in cycle $C{\prime }_4$ or $C\prime {\prime }_4,$ d(v) = 2. Let $u\in V(Q_n-F-C{\prime }_4-C\prime {\prime }_4).$ If u and u₁ have common neighbors, then u and u₂ or u₄ have no common neighbors, otherwise, there would be a cycle with length 5 in Q_n. Since $|N_{Q_n}(u)\cap \{N_{Q_n}(u_1)\cup N_{Q_n}(u_2)\left\}\right|\le 2$ and $|N_{Q_n}(u)\cap \{N_{Q_n}(u_3)\cup N_{Q_n}(u_4)\left\}\right|\le 2,$ we have $|N_{Q_n}(u)\cap \{N_{Q_n}(V(C{\prime }_4))\cup N_{Q_n}(V(C\prime {\prime }_4))\left\}\right|\le 8.$ Since Q_n is n-regular and $n-8\ge 3,$ it follows that u has at least two neighbors. So $c{\kappa }_{2,3}(Q_n)\le 8n-24$ for $n\ge 11.$ □

Figure 2. Graph Explanation of Lemma 3.1.

Figure 3. Graph Explanation of Case 1.

Lemma 3.2.

Let Q_n be an n-dimension hypercube. Then $c{\kappa }_{2,3}(Q_n)\ge 8n-24$ for $n\ge 11.$

Proof.

Let F be a 2-good 3-component cut of Q_n and $\left|F\right|\le 8n-25.$ Let $F^0=F\cap Q_{n-1}^0$ and $F^1=F\cap Q_{n-1}^1.$ Then $F=F^0\cup F^1.$ Without loss of generality, suppose that $\left|F^0\right|\le \left|F^1\right|.$ Since $\left|F\right|=\left|F^0\right|+\left|F^1\right|\le 8n-25,$ we have $\left|F^0\right|\le 4n-13=4(n-1)-9<5n-14$ for $n\ge 4.$ By Lemma 2.3, we consider the following cases:

Case 1. $Q_{n-1}^0-F^0$ is connected.

Since F is a 2-good 3-component cut, we have $Q_{n-1}^1-F^1$ is disconnected and $Q_n-F$ exists two connected components, denoted by W₁ and W₂. There is no cycle with length 3 in Q_n, so W₁ and W₂ contain at least a cycle with length 4. By the structure of Q_n, each vertex in $Q_{n-1}^1$ has an outer neighbor in $Q_{n-1}^0,$ thus $8\le |V(W_1)|+|V(W_2)|\le \left|F^0\right|\le 4n-13.$ It is clear that $N_{Q_n}(V(W_1))\cap V(W_2)=\varnothing$ and $N_{Q_n}(V(W_2))\cap V(W_1)=\varnothing ,$ so $|N_{Q_n}(V(W_1))\cup N_{Q_n}(V(W_2))|=\left|N_{Q_n}\right\{V(W_1\cup W_2)\left\}\right|,$ see Figure 3. Let $T_1=V(W_1\cup W_2)$ and $\left|T_1\right|=t$ for $8\le t\le 4n-13.$ We have $|N_{Q_n}(T_1)|>8n-25$ for $8\le t\le 4n-13$ and $n\ge 11.$ Since $|V(Q_n)-(T_1\cup Q_n(T_1))|\ge 2^n-(4n-13)-(8n-25)>4n-13\ge \left|T_1\right|,$ it follows that $|N_{Q_n}(T_1)|>q_n(2n)$ for $2n<t\le 4n-13$ by Lemma 2.4. According to Lemma 2.1, $|N_{Q_n}(T_1)|>p_n(t)$ for $8<t\le n+1$ and $|N_{Q_n}(T_1)|>q_n(t)$ for $n+2<t\le 2n$ when $n\ge 11.$ The minimum value of these two quadratic functions $p_n(t)$ and $q_n(t)$ is min $\{p_n(8),p_n(n+1),q_n(n+2),q_n(2n)\}=p_n(8)$ for $n\ge 11.$ The quadratic gets the minimum value if and only if $\left|T_1\right|=|V(W_1)|+|V(W_2)|=8.$ In this case, W₁ and W₂ are exactly two cycles with length 4 in $Q_n-F.$ By Lemma 2.5, we have $|N_{Q_n}(V(W_1))\cup N_{Q_n}(V(W_2))|\ge 8(n-2)-8=8n-24.$ It follows that $\left|F\right|\ge |N_{Q_n}(V(W_1))\cup N_{Q_n}(V(W_2))|\ge 8n-24,$ and a contradiction is obtained.

Case 2. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and remaining small components containing at most four vertices in total.

Since F is a 2-good 3-component cut and each vertex in $Q_{n-1}^0$ only has one outer neighbor in $Q_{n-1}^1,$ the connected components of $Q_{n-1}^0-F^0$ contain no isolated vertices. The graphs with no isolated vertices induced by at most 4 vertices are shown in Figure 4. We divide into the following four cases for discussion.

Subcase 2.1. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and a path P₂ (Figure 4(a)), denoted by $v^1{v}^2.$

Figure 4. The graphs with no isolated vertices induced by at most 4 vertices.

Figure 5. Graph introduction to Subcase 2.1.

There are at least two connected components in $Q_{n-1}^1-F^1,$ one of which contains the outer neighbors of v¹ and v², denoted by W₃, and another connected component which is also the connected component of $Q_n-F,$ denoted by W₄. Let $W{\prime }_3=W_3\cup \left\{v^1{v}^2\right\}$ and $W{\prime }_3$ is a connected component of $Q_n-F,$ see Figure 5. It is obvious that $N_{Q_{n-1}^1}(V(W_3))\cap V(W_4)=\varnothing$ and $N_{Q_{n-1}^1}(V(W_4))\cap V(W_3)=\varnothing ,$ so $N_{Q_{n-1}^1}\{V(W_3)\cup V(W_4)\}=N_{Q_{n-1}^1}(V(W_4))\cup N_{Q_{n-1}^1}(V(W_3)).$ Let $T_2=V(W_3\cup W_4)$ and $\left|T_2\right|=t\prime .$ Since each vertex in $Q_{n-1}^1$ has an outer neighbor in $Q_{n-1}^0,$ we have $N_{Q_{n-1}^0}\{V(W_3\cup W_4)\}\subseteq F^0\cup \{v^1,v^2\}.$ So $t\prime =|V(W_3\cup W_4)|\le 4n-15.$ The following discussion is similar to Case 1, where the quadratic function $p_n(t\prime )$ gets the minimum value at $t\prime =8.$ Then connected components W₃ and W₄ are cycles with length 4 in $Q_n-F.$ By Lemma 2.5, we have $|N_{Q_n}(V(W_3))\cup N_{Q_n}(V(W_4))|\ge 8(n-2)-8=8n-24.$ It follows that $\left|F\right|\ge |N_{Q_n}(V(W_3))\cup N_{Q_n}(V(W_4))|\ge 8n-24,$ and a contradiction is obtained.

Subcase 2.2. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and a path P₃ (Figure 4(b)), denoted by $v^3{v}^4{v}^5.$

In $Q_{n-1}^1-F^1,$ there are at least two connected components, denoted by W₅ and W₆. Without loss of generality, suppose that W₅ contains outer neighbors of v³, v⁴ and v⁵. Since $N_{Q_{n-1}^0}\{V(W_5\cup W_6)\}\subseteq F^0\cup \{v^3,v^4,v^5\},$ it follows that $|V(W_5\cup W_6)|\le 4n-16.$ It is the same as the discussion in Subcase 2.1, and a contradiction is obtained.

Subcase 2.3. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and a cycle with length 4 (Figure 4(c)), denoted by $C=u^1{u}^2{u}^3{u}^4{u}^1.$

There are at least two connected components in $Q_{n-1}^1-F^1,$ denoted by W₇ and W₈. If C is a connected component of $Q_n-F,$ then $N_{Q_{n-1}^0}\{V(W_7\cup W_8)\}\subseteq F^0.$ So $|V(W_7\cup W_8)|\le 4n-13.$ Then from the same reason as Subcase 2.1, we get a contradiction. If C is not a connected component of $Q_n-F,$ then $N_{Q_{n-1}^0}\{V(W_7\cup W_8)\}\subseteq F^0\cup \{u_1,u_2,u_3,u_4\}.$ So $|V(W_7\cup W_8)|\le 4n-17.$ It is the same as the discussion in Subcase 2.1, and a contradiction is obtained.

Subcase 2.4. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and a path P₄ (Figure 4(d)), denoted by $v^6{v}^7{v}^8{v}^9.$

There are at least two connected components in $Q_{n-1}^1-F^1,$ denoted by W₇ and W₈. Hence we have $N_{Q_{n-1}^0}\{V(W_7\cup W_8)\}\subseteq F^0\cup \{v^6,v^7,v^8,v^9\},$ it follows that $|V(W_7\cup W_8)|\le 4n-17.$ It is similar to the above discussion in Subcase 2.1 and a contradiction is obtained. The proof is the same as the other two subgraphs (Figure 4(e) and (f)), we just prove the path P₄. □

By Lemma 3.1 and Lemma 3.2, the following theorem is established.

Theorem 3.3.

Let Q_n be an n-dimension hypercube. Then $c{\kappa }_{2,3}(Q_n)=8n-24$ for $n\ge 11.$

4. g-extra r-component connectivity

Lemma 4.1.

Let Q_n be an n-dimension hypercube. Then $c{\kappa }_3^2(Q_n)\le 6n-20$ for $n\ge 9.$

Proof.

Let $u_1=000000,\dots ,0,u_2=100000,\dots ,0,$ $u_3=100010,\dots ,0$ and $v_1=0000110,\dots ,0,$ $v_2=1000110,\dots ,0,v_3=1000100,\dots ,0.$ Let $F=N_{Q_n}\{u_1,u_2,u_3\}\cup N_{Q_n}\{v_1,v_2,v_3\}.$ Then $\left|F\right|=4(n-1)+2(n-2)-2\times 5-1\times 2=6n-20,$ see Figure 6. There are at least three connected components in $Q_n-F,$ two of which are paths with length 3, denoted by $u_1{u}_2{u}_3$ and $v_1{v}_2{v}_3,$ respectively. Since Q_n is bipartite, there is no odd cycle in Q_n. For any $w\in V(Q_n-F-\{u_1{u}_2{u}_3,v_1{v}_2{v}_3\}),$ $|N_{Q_n}(w)\cap F|\le 8.$ When $|N_{Q_n}(w)\cap F|=8,$ w has two common neighbors with $u_1,u_3,v_1$ and v₃. It follows that w has a neighbor $w\prime$ in $Q_n-F$ because the regularity of Q_n is $n(n\ge 9).$ The vertex $w\prime$ has at most two common neighbors with u₂ and v₂, respectively. Then $|N_{Q_n}(w\prime )\cap F|\le 4,$ we have $w\prime$ have at least 5 neighbors in $Q_n-F.$ So every connected component of $Q_n-F$ has at least three vertices, thus $c{\kappa }_3^2(Q_n)\le 6n-20$ for $n\ge 9.$ □

Figure 6. Graph Explanation of Lemma 4.1.

Lemma 4.2.

Let Q_n be an n-dimension hypercube. Then $c{\kappa }_3^2(Q_n)\ge 6n-20$ for $n\ge 9.$

Proof.

Suppose that F is a 2-extra 3-component cut and $\left|F\right|\le 6n-21.$ Let $F^0=F\cap Q_{n-1}^0$ and $F^1=F\cap Q_{n-1}^1.$ Without loss of generality, suppose that $\left|F^0\right|\le \left|F^1\right|.$ Since $\left|F\right|=\left|F^0\right|+\left|F^1\right|\le 6n-21,$ we have $\left|F^0\right|\le 3n-11=3(n-1)-8<3n-5.$ By Lemma 2.2, we consider the following cases:

Case 1. $Q_{n-1}^0-F^0$ is connected.

Since F is a 2-extra 3-component cut, we have $Q_{n-1}^1-F^1$ is disconnected and exists two connected components in $Q_n-F,$ denoted by S₁ and S₂. It is clear that $6\le |V(S_1)|+|V(S_2)|\le \left|F^0\right|\le 3n-11.$ Since $N_{Q_n}(V(S_1))\cap V(S_2)=\varnothing$ and $N_{Q_n}(V(S_2))\cap V(S_1)=\varnothing ,$ it follows that $|N_{Q_n}(V(S_1))\cup N_{Q_n}(V(S_2))|=\left|N_{Q_n}\right\{V(S_1\cup S_2)\left\}\right|.$ Let $T=V(S_1\cup S_2)$ and $\left|T\right|=t$ for $6\le t\le 3n-11.$ We have $|N_{Q_n}(T)|>6n-21$ for $6\le t\le 3n-11$ and $n\ge 9.$ Since $|V(Q_n)-(T\cup Q_n(T))|\ge 2^n-(3n-11)-(6n-21)>3n-11\ge \left|T\right|,$ it follows that $|N_{Q_n}(T)|>q_n(2n)$ for $2n<t\le 3n-11$ by Lemma 2.4. By Lemma 2.1, $|N_{Q_n}(T)|>p_n(t)$ for $6<t\le n+1$ and $|N_{Q_n}(T)|>q_n(t)$ for $n+2<t\le 2n$ when $n\ge 9.$ The minimum value of these two quadratic functions $p_n(t)$ and $q_n(t)$ is min $\{p_n(6),p_n(n+1),q_n(n+2),q_n(2n)\}=p_n(6)$ for $n\ge 9.$ The quadratic gets the minimum value if and only if $\left|T\right|=|V(S_1)|+|V(S_2)|=6.$ In this case, S₁ and S₂ are paths with length 3 in $Q_n-F.$ By Lemma 2.6, we have $|N_{Q_n}(V(S_1))\cup N_{Q_n}(V(S_2))|\ge 6n-20.$ Hence $\left|F\right|\ge |N_{Q_n}(V(S_1))\cup N_{Q_n}(V(S_2))|\ge 6n-20,$ and a contradiction is obtained.

Case 2. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and remaining small components containing at most two vertices in total.

Subcase 2.1. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and an isolated vertex, denoted by v₁.

In $Q_{n-1}^1-F^1,$ there are at least two connected components, denoted by S₃ and S₄. Since $N_{Q_{n-1}^0}\{V(S_3\cup S_4)\}\subseteq F^0\cup \left\{v_1\right\},$ it follows that $|V(S_3\cup S_4)|\le 3n-12.$ It is similar to Case 1, and a contradiction is obtained.

Subcase 2.2. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and two isolated vertices, denoted by v₂ and v₃.

There are at least two connected components in $Q_{n-1}^1-F^1,$ denoted by S₅ and S₆. Since $N_{Q_{n-1}^0}\{V(S_5\cup S_6)\}\subseteq F^0\cup \{v_2,v_2\},$ it follows that $|V(S_5\cup S_6)|\le 3n-13.$ It is similar to Case 1 and a contradiction is obtained.

Subcase 2.3. $Q_{n-1}^0-F^0$ is disconnected with a large connected component and a path P₂, denoted by $v_4{v}_5.$

This proof is the same as Subcase 2.2. □

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

Theorem 4.3.

Let Q_n be an n-dimension hypercube. Then $c{\kappa }_3^2(Q_n)=6n-20$ for $n\ge 9.$

5. Concluding remarks

In this paper, we obtain $c{\kappa }_{2,3}(Q_n)=8n-24$ when $n\ge 11$ and $c{\kappa }_3^2(Q_n)=6n-20$ when $n\ge 9.$ These questions still remain open, we can consider more general results like $c{\kappa }_{2,r}(Q_n)=?$ and $c{\kappa }_r^2(Q_n)=?$ Other forms of the novel connectivity can also be considered, which are valuable for measuring the fault tolerance of interconnection networks.

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability

The data used to support the findings of this study are available from the corresponding author upon request.

Additional information

Funding

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