Reliability Analysis of Varietal Hypercube

Guiyu Shi, Ganghua Xie, Yinkui Li^*

Department of Mathematics, Qinghai Nationalities University, Xining, China.

DOI: 10.4236/am.2024.154016                

Abstract

Connectivity is a vital metric to explore fault tolerance and reliability of network structure based on a graph model. Let be a connected graph. A connected graph G is called supper-κ (resp. supper-λ) if every minimum vertex cut (edge cut) of G is the set of neighbors of some vertex in G. The g-component connectivity of a graph G, denoted by , is the minimum number of vertices whose removal from G results in a disconnected graph with at least g components or a graph with fewer than g vertices. The g-component edge connectivity can be defined similarly. In this paper, we determine the g-component (edge) connectivity of varietal hypercube for small g.

Keywords

Interconnection Networks, Fault Tolerance, g-Component Connectivity

1. Introduction

Graph connectivity is an important topological parameter that reflects the graph structure, and is usually used to evaluate the vulnerability, reliability and fault tolerance of the corresponding network [1] . Given a graph $G=\left(V\mathrm{,}E\right)$ with vertex set V and edge set E, we use V stand for the set of network nodes and E the set of communication links between nodes. The vertex-cut of a connected graph G is the subset $F\subseteq V$ that make $G-F$ disconnected. The cardinality of the smallest vertex-cut set of a graph G is called the connectivity of the graph G, denoted by $\kappa \left(G\right)$ . In order to further analyze the detailed situation of disconnected graphs caused by vertex-cut, Harary [2] suggested studying the conditional connectivity with additional restrictions on the vertex-cut F and (or) the component of $G-F$ . In 1984, Chartrand et al. [3] [4] proposed the concepts of component connectivity, which is essentially extensions of traditional connectivity, so it can also be regarded as a kind of conditional connectivity.

For any positive integer g, the g-component cut of the graph G is a vertex set $F\subseteq V$ such that $G-F$ has at least $g\left(g\ge 2\right)$ components. The g-component connectivity of graph G, denoted by $c{\kappa }_g\left(G\right)$ , is the cardinality of a minimum g-component cut of graph G, that is, $c{\kappa }_g\left(G\right)=\min \left\{\left|F\right|\mathrm{<mo>\; :\; </mo>}F\subseteq V\mathrm{,}\omega \left(G-F\right)\ge g\right\}$ . Of course, we define that $c{\kappa }_g\left(G\right)=0$ if G is a complete graph $K_n$ or a disconnected graph. Obviously, $c{\kappa }_2\left(G\right)=\kappa \left(G\right)$ and $c{\kappa }_g\left(G\right)\le c{\kappa }_{g+1}\left(G\right)$ .

In [5] [6] [7] , authors determined the g-component connectivity of n-dimensional bubble-sort star graph $B{S}_n$ , n-dimensional burnt pancake graph $B{P}_n$ , the hierarchical star networks $H{S}_n$ , the alternating Group graphs $A{G}_n$ and split star graph $S_2^n$ . Zhao et al. [8] [9] and Xu et al. [10] respectively determined the g-component connectivity of Cayley graphs generated by n-dimensional folded hypercube $F{Q}_n$ , n-dimensional dual cube $D_n$ and transposition tree. In addition, Chang et al. [11] determined the g-component connectivity of alternating group networks $A{N}_n$ when $g=\mathrm{3,4}$ . Ding et al. [12] dealt with the g-component (edge) connectivity of shuffle-cubes $S{Q}_n$ for small g. Recently, Li et al. [13] studied the relationship between extra connectivity and component connectivity of general networks, and Hao et al. [14] and Guo et al. [15] independently proposed the relationship between extra edge connectivity and component connectivity of regular networks in the literature.

All graphs considered in this paper are finite and simple. We refer to the book [16] for graph theoretical notation and terminology not described here. For the graph G, let $e\left(G\right)$ , $n\left(G\right)$ , $\bar{G}$ , and $\omega \left(G\right)$ represent respectively the size, the order, the complement and the number of components of G. Let $G=\left(V\mathrm{,}E\right)$ be a connected graph, $N_G\left(v\right)$ the neighbors of a vertex v in G (simply $N\left(v\right)$ ), $E\left(v\right)$ the edges incident to v. For $X\mathrm{,}Y\subset V$ , denote by $\left[X\mathrm{,}Y\right]$ the set of edges of G with one end in X and tie other in Y. We call G k-regular if $d_G\left(u\right)=k$ for every vertex $u\in V\left(G\right)$ . By $\delta \left(G\right)$ and $\Delta \left(G\right)$ denote the minimum and maximum degree of the graph G, respectively. By $\left|S\right|$ denote the number of elements in S and $N_G\left(S\right)$ denote the set of vertices of G which has neighbour vertex in S, that means $N_G\left(S\right)={\cup }_{v\in S}{N}_G\left(v\right)\backslash S$ .

2. Preliminary

Definition 1 [17] The n-dimensional hypercube is a connected graph with $2^n$ vertices and denoted by $Q_n$ . The vertex set $V\left(Q_n\right)=\{x_1{x}_2\cdots x_n\mathrm{<mo>\; :\; </mo>}{x}_i=0$ or $\mathrm{1,1}\le i\le n\}$ . Two vertices $u=u_1{u}_2\cdots u_n$ and $v=v_1{v}_2\cdots v_n$ in $Q_n$ are adjacent if and only they differ in exact one position.

Definition 2 [18] The n-dimensional varietal hypercube, denoted by $V{Q}_n$ , has $2^n$ vertices, each labeled by an n-bit binary string and $V\left(V{Q}_n\right)=\{x_n{x}_{n-1}\cdots x_2{x}_1\mathrm{<mo>\; :\; </mo>}{x}_i=0$ or $\mathrm{1,}i=\mathrm{1,2,}\cdots \mathrm{,}n\}$ . $V{Q}_1$ is a complete graph $K_2$ of two vertices labeled with 0 and 1, respectively. For $n\ge 2$ , $V{Q}_n$ can be recursively constructed from two copies of $V{Q}_{n-1}$ , denoted by $V{Q}_{n-1}^0$ and $V{Q}_{n-1}^1$ , and by adding $2^{n-1}$ edges between $V{Q}_{n-1}^0$ and $V{Q}_{n-1}^1$ , where $V\left(V{Q}_{n-1}^0\right)=\{0x_{n-1}\cdots x_2{x}_1:x_i=0$ or $1,i=1,2,\cdots ,n\}$ , $V\left(V{Q}_{n-1}^1\right)=\{1x_{n-1}\cdots x_2{x}_1:x_i=0$ or $1,i=1,2,\cdots ,n\}$ . The vertex $x=0x_{n-1}{x}_{n-2}{x}_{n-3}\cdots x_2{x}_1\in V\left(V{Q}_{n-1}^0\right)$ is adjacent to the vertex $y=0y_{n-1}{y}_{n-2}{y}_{n-3}\cdots y_2{y}_1\in V\left(V{Q}_{n-1}^1\right)$ if and only if

1) $x_{n-1}{x}_{n-2}{x}_{n-3}\cdots x_2{x}_1=y_{n-1}{y}_{n-2}{y}_{n-3}\cdots y_2{y}_1$ if $3\nmid n$ , or;

2) $x_{n-3}\cdots x_2{x}_1=y_{n-3}\cdots y_2{y}_1$ and $\left(x_{n-1}{x}_{n-2}\mathrm{,}{y}_{n-1}{y}_{n-2}\right)\in \left\{\left(\mathrm{00,00}\right)\mathrm{,}\left(\mathrm{01,01}\right)\mathrm{,}\left(\mathrm{10,11}\right)\mathrm{,}\left(\mathrm{11,10}\right)\right\}$ if $\mathrm{3\; <mo>\; |\; </mo>}n$ .

Obviously, $V{Q}_n$ is an n-regular and its girth is 4. Moreover, it contains circles of length 5 when $n\ge 3$ [19] [20] . The varietal hypercube $V{Q}_1$ , $V{Q}_2$ , $V{Q}_3$ are illustrated in Figure 1.

From the definition, we can see that each vertex of $V{Q}_n$ with a leading 0 bit has exactly one neighbor with a leading 1 and vice versa. In fact, some pairs of parallel edge are changed to some pairs of cross edges. Furthermore, $V{Q}_n$ can be obtained by adding a perfect matching M between $V{Q}_{n-1}^0$ and $V{Q}_{n-1}^1$ . Hence $V{Q}_n$ can be viewed as $G(V{Q}_{n-1}^0\mathrm{,}V{Q}_{n-1}^1\mathrm{,}M$ or $V{Q}_{n-1}^0\odot V{Q}_{n-1}^1$ briefly. For any vertex $u\in V\left(V{Q}_n\right)$ , $e_M\left(u\right)$ is the esge incident to u in M.

As a variant of the hypercube, the n-dimensional varietal hypercube $V{Q}_n$ , which has the same number of vertices and edges as $Q_n$ , not only has the most ideal characteristics of $Q_n$ , including some characteristics such as recursive structure, strong connectivity, and symmetry but also has a smaller diameter than $Q_n$ , and its average distance is smaller than the hypercube [18] .

Proposition 1 [18] $diam\left(V{Q}_n\right)=\lceil 2n/3\rceil$ for $n\ge 3$ .

Proposition 2 [21] [22] [23] $V{Q}_n$ is a vertex-transitive and edge-transitive.

Proposition 3 [19] $\kappa \left(V{Q}_n\right)=\lambda \left(V{Q}_n\right)=n$ for $n\ge 1$ .

Proposition 4 [24] Any two vertices of $Q_n$ have exactly two common neighbors for $n\ge 3$ if they have any.

Proposition 5 [25] Let x and y be any two vertices of $V\left(Q_n\right)\left(n\ge 3\right)$ such that have two common neighbors.

Figure 1. The varietal hypercube $V{Q}_1$ , $V{Q}_2$ , $V{Q}_3$ , and $V{Q}_4$ .

1) If $x\in V\left(Q_{n-1}^0\right)$ , $y\in V\left(Q_{n-1}^1\right)$ , then the one common neighbor is in $Q_{n-1}^0$ , and the other one is in $Q_{n-1}^1$ .

2) If $x\mathrm{,}y\in V\left(Q_{n-1}^0\right)$ or $V\left(Q_{n-1}^1\right)$ , then the two common neighbors are in $Q_{n-1}^0$ or $Q_{n-1}^1$ .

3. Main Result

The varietal hypercube $V{Q}_n$ has an important property as follows.

The varietal hypercube is obtained by interchanging a pair of edges of the hypercube. Then it appears two vertices which have only one common neighbor. So we have the following result similar to proposition 4.

Theorem 1. Any two vertices of $V{Q}_n$ have at most two common neighbors for $\left(n\ge 3\right)$ if they have.

Corollary 2. For any two vertices $x\mathrm{,}y\in V\left(vV{Q}_n\right)\left(n\ge 3\right)$ ,

1) if $d\left(x\mathrm{,}y\right)=2$ , then they have at most two common neighbors;

2) if $d\left(x\mathrm{,}y\right)\ne 2$ , then they do not have common neighbors.

According to the definition of $V{Q}_n$ , if any two vertices of $V\left(V{Q}_n\right)$ have only one common neighbor, then it is obtained by interchanging a pair of edges of the hypercube. Hence similar to proposition 5, we have

Theorem 3. Let x and y be any two vertices of $V\left(V{Q}_n\right)\left(n\ge 3\right)$ such that have only two common neighbors.

1) If $x\in V\left(V{Q}_{n-1}^0\right)$ , $y\in V\left(V{Q}_{n-1}^1\right)$ , then the one common neighbor is in $V{Q}_{n-1}^0$ , and the other one is in $V{Q}_{n-1}^1$ .

2) If $x\mathrm{,}y\in V\left(V{Q}_{n-1}^0\right)$ or $V\left(V{Q}_{n-1}^1\right)$ , then the two common neighbors are in $V{Q}_{n-1}^0$ or $V{Q}_{n-1}^1$ .

By the definition of $V{Q}_n$ and above results, we have:

Theorem 4. If any two vertices of $V\left(V{Q}_n\right)$ have only one common neighbor, then the two vertices and their common neighbor are in some $V{Q}_3$ .

In [19] , Xu et al., proved that $V{Q}_n$ is super-λ and super-κ. Here, we present another proof of this result.

Theorem 5. $V{Q}_n$ is super-λ for $n\ge 3$ .

By induction. It is true $n\le 4$ . Let $n\ge 5$ . Assume that it holds for $n<k$ .We will show that it is true for $n=k$ .

Let $F\subseteq E\left(V{Q}_n\right)$ , $\left|F\right|=n$ and $V{Q}_n-F$ be not connected. Furthermore, $V{Q}_n-F$ has only two connected components. Without loss of generality, suppose $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le \lfloor n/2\rfloor$ . Then $V{Q}_{n-1}^0-F$ is connected.

Note that $\left|\left[V{Q}_{n-1}^0,V{Q}_{n-1}^1\right]\right|=2^{n-1}>n$ ( $n\ge 5$ ). If $V{Q}_{n-1}^1-F$ is connected, then $V{Q}_n-F$ is connected, a contradiction.

Assume that $V{Q}_{n-1}^1-F$ is not connected. We have $\left|F\cap E\left(V{Q}_{n-1}^1\right)\right|\ge n-1$ . If $\left|F\cap E\left(V{Q}_{n-1}^1\right)\right|=n$ , then $F\cap E\left(V{Q}_{n-1}^0\right)=\varnothing$ and $\left[V{Q}_{n-1}^0\mathrm{,}V{Q}_{n-1}^1\right]\cap F=\varnothing$ . And each vertex of $V{Q}_{n-1}^1-F$ has one neighbor in $V{Q}_{n-1}^0-F$ , that is, $V{Q}_n-F$ is connected, a contradiction.

Hence $\left|F\cap E\left(V{Q}_{n-1}^1\right)\right|=n-1$ . According to the inductive hypothesis, $V{Q}_{n-1}^1-F$ is super-λ. Suppose the isolated vertex x and $G_1$ are the only two components of $V{Q}_{n-1}^1-F$ . And $G_1$ is connected to $V{Q}_{n-1}^0-F$ . If $e_M\left(x\right)\notin F$ , then $V{Q}_n-F$ is connected, a contradiction. So $e_M\left(x\right)\in F$ . We have $F=e\left(x\right)$ and $V{Q}_n-F$ has only two components, one component ia x. Hence $V{Q}_n$ is super-λ.

Theorem 6. $V{Q}_n$ is super-κ for $n\ge 3$ .

The proof is similar to Theorem 5.

Theorem 7. $c{\kappa }_2\left(V{Q}_n\right)=\kappa \left(V{Q}_n\right)=n$ for $n\ge 2$ .

By definition of $c{\kappa }_g\left(G\right)$ , we have $c{\kappa }_2\left(V{Q}_n\right)=\kappa \left(V{Q}_n\right)$ , and we have $\kappa \left(V{Q}_n\right)=n$ for $n\ge 1$ by proposition 3, thus $c{\kappa }_2\left(V{Q}_n\right)=\kappa \left(V{Q}_n\right)=n$ for $n\ge 2$ .

Theorem 8. $c{\kappa }_3\left(V{Q}_n\right)=2n-2$ for $n\ge 3$ .

We choose two nonadjacent vertices x, y in a cycle $C_4$ which has two common neighbors. Then $V{Q}_n-N\left(\left\{x\mathrm{,}y\right\}\right)$ has at least three connected components and $\left|N\left(\left\{x\mathrm{,}y\right\}\right)\right|=2n-2$ . That is $c{\kappa }_3\left(V{Q}_n\right)\le 2n-2$ .

We will show $c{\kappa }_3\left(V{Q}_n\right)\ge 2n-2$ by induction. It is easy to check that it is true for $n=\mathrm{3,4}$ . So we suppose $n\ge 5$ . Suppose it is true for $n<k$ . Let $n=k$ .

Let $F\subseteq V\left(V{Q}_n\right)$ with $\left|F\right|\le 2n-3$ . And $V{Q}_n-F$ has at least three connected components, say, $G_1$ , $G_2$ , $G_3$ . We have $\left|F\cap V\left(V{Q}_{n-1}^0\right)\right|\le n-2$ or $\left|F\cap V\left(V{Q}_{n-1}^0\right)\right|\le n-2$ . Without loss of generality, we set $\left|F\cap V\left(V{Q}_{n-1}^0\right)\right|\le n-2$ . Hence $V{Q}_{n-1}^0-F$ is connected.

If $V{Q}_{n-1}^1-F$ has at least three components, from the inductive hypothesis, then $\left|F\cap V\left(V{Q}_{n-1}^1\right)\right|\ge 2n-4$ and $\left|F\cap V\left(V{Q}_{n-1}^0\right)\right|\le 1$ . Because each vertex of $V{Q}_{n-1}^1$ has one neighbor in $V{Q}_{n-1}^0$ , at most one vertex of $V{Q}_{n-1}^1-F$ has no neighbors in $V{Q}_{n-1}^0$ . So $V{Q}_n-F$ has at most two connected components, a contradiction.

Hence $V{Q}_{n-1}^1-F$ has at most two components. At most one component of $V{Q}_{n-1}^1-F$ is not connected to $V{Q}_{n-1}^0-F$ . And $V{Q}_n-F$ has at most two connected components, a contradiction.

Theorem 9. $c{\lambda }_2\left(V{Q}_n\right)=\lambda \left(V{Q}_n\right)=n$ for $n\ge 2$ .

By definition of $c{\lambda }_g\left(G\right)$ , we have $c{\lambda }_2\left(V{Q}_n\right)=\lambda \left(V{Q}_n\right)$ , and we have $\lambda \left(V{Q}_n\right)=n$ for $n\ge 1$ by proposition 3, thus $c{\lambda }_2\left(V{Q}_n\right)=\lambda \left(V{Q}_n\right)=n$ for $n\ge 2$ .

Theorem 10. $c{\lambda }_3\left(V{Q}_n\right)=2n-1$ for $n\ge 2$ .

Take an edge $e=uv$ , then $\left|E\left(u\right)\cup E\left(v\right)\right|=2n-1$ . And $V{Q}_n-E\left(u\right)-E\left(v\right)$ has at least three connected components. That is $c{\lambda }_3\left(V{Q}_n\right)\le 2n-1$ .

Next we will show that $c{\lambda }_3\left(V{Q}_n\right)\ge 2n-1$ by induction. It is easy to check it is true for $n=\mathrm{2,3,4}$ . So we suppose $n\ge 5$ . Suppose it is true for all $n<k$ . We will prove that is true for $n=k$ .

Let $F\subseteq E\left(V{Q}_n\right)$ with $\left|F\right|\le 2n-2$ , and $V{Q}_n-F$ has at least three components. Now since $V{Q}_{n-1}^0\odot V{Q}_{n-1}^1$ , we have $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le n-1$ or $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le n-1$ , say, $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le n-1$ . Since $\lambda \left(V{Q}_{n-1}\right)=n-1$ , we have two cases.

Case 1 $V{Q}_{n-1}^0-F$ is not connected.

Then $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|=n-1$ and $V{Q}_{n-1}^0-F$ has only two components.

If $V{Q}_{n-1}^1-F$ is not connected, then $\left|F\cap E\left(V{Q}_{n-1}^1\right)\right|=n-1$ . That is $\left[V{Q}_{n-1}^0\mathrm{,}V{Q}_{n-1}^1\right]\cap F=\varnothing$ . But each vertex of $V{Q}_{n-1}^1-F$ is connected to one component of $V{Q}_{n-1}^0-F$ . Hence $V{Q}_n-F$ has only two components, a contradiction.

Note that $\left|\left[V{Q}_{n-1}^0,V{Q}_{n-1}^1\right]\right|=2^{n-1}>n-1$ ( $n\ge 5$ ). If $V{Q}_{n-1}^1-F$ is connected, then $V{Q}_{n-1}^1-F$ is connected to one component of $V{Q}_{n-1}^0-F$ . Hence $V{Q}_n-F$ has only two components, a contradiction.

Case 2 $V{Q}_{n-1}^0-F$ is connected.

If $V{Q}_{n-1}^1-F$ is connected, then we are done. We assume that $V{Q}_{n-1}^1-F$ is not connected. And $V{Q}_{n-1}^1-F$ has at most one isolated vertex since $\left|F\right|\le 2n-2$ .

If $V{Q}_{n-1}^1-F$ has at least three components, from the inductive hypothesis, then $\left|F\cap E\left(V{Q}_{n-1}^1\right)\right|\ge 2n-3$ . Hence at most one of components of $V{Q}_{n-1}^1-F$ is not connected to $V{Q}_{n-1}^0-F$ , $V{Q}_n-F$ has at most two components, a contradiction.

Therefore we assume that $V{Q}_{n-1}^1-F$ has only two components. But $2^{n-1}-\left(2n-2\right)>0$ ( $n\ge 5$ ), $V{Q}_n-F$ has at most two components, a contradiction.

Theorem 11. $c{\lambda }_4\left(V{Q}_n\right)=3n-2$ for $n\ge 2$ .

Take a path $P_3=uvw$ . Then $\left|E\left(u\right)\cup E\left(v\right)\cup E\left(w\right)\right|=2n-1$ . And $V{Q}_n-E\left(u\right)-E\left(v\right)-E\left(w\right)$ has at least four connected components. That is $c{\lambda }_4\left(V{Q}_n\right)\le 3n-2$ .

Next we will show that $c{\lambda }_3\left(V{Q}_n\right)\ge 2n-1$ by induction. It is easy to check it is true for $n=\mathrm{2,3,4}$ . So we suppose $n\ge 5$ . Suppose it is true for all $n<k$ . We will prove that is true for $n=k$ .

Let $F\subseteq E\left(V{Q}_n\right)$ with $\left|F\right|\le 3n-3$ , and $V{Q}_n-F$ has at least four components. Now since $V{Q}_{n-1}^0\odot V{Q}_{n-1}^1$ , we have $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le \left[3n/2\right]-2$ or $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le \left[3n/2\right]-2$ , say, $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le \left[3n/2\right]-2$ . Since $c{\lambda }_3\left(V{Q}_{n-1}\right)=2n-3>\left[3n/2\right]-2$ ( $n\ge 5$ ), $V{Q}_{n-1}^0-F$ has at most two components.

Case 1 $V{Q}_{n-1}^0-F$ is connected.

If $V{Q}_{n-1}^1-F$ has at least four components, then $c{\lambda }_4\left(V{Q}_{n-1}\right)\ge 3n-5$ by the inductive hypothesis. We need delete at most two edges again. Since each vertex of $V{Q}_{n-1}^1$ has a neighbor in $V{Q}_{n-1}^0$ and $\left|\left[V{Q}_{n-1}^0,V{Q}_{n-1}^1\right]\right|=2^{n-1}>2$ ( $n\ge 5$ ), $V{Q}_n-F$ has at most three components, a contradiction.

Suppose $V{Q}_{n-1}^1-F$ has at most three components. Because of $\left|\left[V{Q}_{n-1}^0,V{Q}_{n-1}^1\right]\right|=2^{n-1}>3n-3$ ( $n\ge 5$ ), $V{Q}_n-F$ has at most three components, a contradiction.

Case 2 $V{Q}_{n-1}^0-F$ has only two connected components.

Then $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\ge \lambda \left(V{Q}_{n-1}\right)=n-1$ and $\left|F\cap E\left(V{Q}_{n-1}^1\right)\right|\le 2n-2$ . Note that $c{\lambda }_3\left(V{Q}_{n-1}\right)=2n-3$ .

If $V{Q}_{n-1}^1-F$ has at least three components, then $\left|F\cap E\left(V{Q}_{n-1}^1\right)\right|\ge 2n-3$ and $\left|F\cap E\left(V{Q}_{n-1}^0\right)\right|\le n$ . But $\left|\left[V{Q}_{n-1}^0\mathrm{,}V{Q}_{n-1}^1\right]\cap F\right|\le 1$ and $2^{n-1}>1$ ( $n\ge 5$ ), $V{Q}_n-F$ has at most three components, a contradiction.

Hence $V{Q}_{n-1}^1-F$ has at most two components. We have $\left|\left[V{Q}_{n-1}^0,V{Q}_{n-1}^1\right]\right|>3n-3\left(n\ge 5\right)$ , and $V{Q}_n-F$ has at most three components, a contradiction.

Acknowledgements

This paper Supported by AFSFQH (2022-ZJ-753), which mainly studies the fault tolerance of operation graph and Mycielskin graph $\mu \left(G\right)$ from the perspective of component connectivity. The next work can be carried out from three aspects: first, study the g-component connectivity of generalized Mycielskin graph. Second, the relationship between the g-component edge connectivity of the graph G and the g-component edge connectivity of the Mycielskin graph $\mu \left(G\right)$ is discussed. Thirdly, the 5-component connectivity of the shuffled cube $S{Q}_n$ and the twisted cube $T{Q}_n$ is discussed.

Funding

Innovative Project (07M2023004).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Hayes, J.P. (2002) Computer Architecture and Organization. McGraw-Hill, Inc. New York.
[2]	Harary, F. (1983) Conditional Connectivity. Networks, 13, 347-357. https://doi.org/10.1002/net.3230130303
[3]	Chartrand, G., Kapoor, S.F., Lesniak, L., et al. (1984) Generalized Connectivity in Graphs. Bulletin, 2, 1-6.
[4]	Sampathkumar, E. (1984) Connectivity of a Graph-A Generalization. Journal of Combinatorics & System Sciences, 9, 71-78.
[5]	Gu, M.-M., Hao, R.-X., Tang, S.-M., et al. (2020) Analysis on Component Connectivity of Bubble-Sort Star Graphs and Burnt Pancake Graphs. Discrete Applied Mathematics, 279, 80-91. https://doi.org/10.1016/j.dam.2019.10.018
[6]	Gu, M.-M., Chang, J.-M. and Hao, R.-X. (2020) On Component Connectivity of Hierarchical Star Networks. International Journal of Foundations of Computer Science, 31, 313-326. https://doi.org/10.1142/S0129054120500100
[7]	Gu, M.M., Hao, R.X. and Chang, J.M. (2019) Measuring the Vulnerability of Alternating Group Graphs and Split-Star Networks in Terms of Component Connectivity. IEEE Access, 7, 97745-97759. https://doi.org/10.1109/ACCESS.2019.2929238
[8]	Zhao, S. and Yang, W. (2019) Conditional Connectivity of Folded Hypercubes. Discrete Applied Mathematics, 257, 388-392. https://doi.org/10.1016/j.dam.2018.09.022
[9]	Zhao, S.-L., Hao, R.-X. and Cheng, E. (2019) Two Kinds of Generalized Connectivity of Dual Cubes. Discrete Applied Mathematics, 257, 306-316. https://doi.org/10.1016/j.dam.2018.09.025
[10]	Xu, L., Zhou, S. and Yang, W. (2020) Component Connectivity of Cayley Graphs Generated by Transposition Trees. International Journal of Parallel, Emergent and Distributed Systems, 35, 103-110. https://doi.org/10.1080/17445760.2019.1618462
[11]	Chang, J.-M., Pai, K.-J., Wu, R.-Y., et al. (2019) The 4-Component Connectivity of Alternating Group Networks. Theoretical Computer Science, 766, 38-45. https://doi.org/10.1016/j.tcs.2018.09.018
[12]	Ding, T., Li, P. and Xu, M. (2020) The Component (Edge) Connectivity of Shuffle-Cubes. Theoretical Computer Science, 835, 108-119. https://doi.org/10.1016/j.tcs.2020.06.015
[13]	Li, X., Lin, C.K., Fan, J., et al. (2021) Relationship between Extra Connectivity and Component Connectivity in Networks. The Computer Journal, 64, 38-53. https://doi.org/10.1093/comjnl/bxz136
[14]	Hao, R.-X., Gu, M.-M. and Chang, J.-M. (2020) Relationship between Extra Edge Connectivity and Component Edge Connectivity for Regular Graphs. Theoretical Computer Science, 833, 41-55. https://doi.org/10.1016/j.tcs.2020.05.006
[15]	Guo, L., Zhang, M., Zhai, S., et al. (2021) Relation of Extra Edge Connectivity and Component Edge Connectivity for Regular Networks. International Journal of Foundations of Computer Science, 32, 137-149. https://doi.org/10.1142/S0129054121500076
[16]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications, Macmillan, London.
[17]	Li, H. and Yang, W. (2013) Bounding the Size of the Subgraph Induced by m Vertices and Extra Edge-Connectivity of Hypercubes. Discrete Applied Mathematics, 161, 2753-2757. https://doi.org/10.1016/j.dam.2013.04.009
[18]	Cheng, S.Y. and Chuang, J.H. (1994) Varietal Hypercube—A New Interconnection Network Topology for Large Scale Multicomputer. Proceedings of 1994 International Conference on Parallel and Distributed Systems, Hsinchu, 19-21 December 1994, 703-708.
[19]	Wang, J.W. and Xu, J.M. (2009) Reliability Analysis of Varietal Hypercube Networks. Journal of University of Science and Technology of China, 39, 1248-1252.
[20]	Cao, J., Li, X. and Xu, J.-M. (2014) Cycles and Paths Embedded in Varietal Hypercubes. Journal of University of Science and Technology of China, 44, 732-737.
[21]	Wang, Y.I., Feng, Y.Q. and Zhou, J.X. (2017) Automorphism Group of the Varietal Hypercube Graph. Graphs and Combinatorics, 33, 1131-1137. https://doi.org/10.1007/s00373-017-1827-y
[22]	Xiao, L., Cao, J. and Xu, J.-M. (2014) Transitivity of Varietal Hypercube Networks. Frontiers of Mathematics in China, 9, 1401-1410. https://doi.org/10.1007/s11464-014-0427-x
[23]	Chang, X., Ma, J. and Yang, D.W. (2021) Symmetric Property and Reliability of Locally Twisted Cubes. Discrete Applied Mathematics, 288, 257-269. https://doi.org/10.1016/j.dam.2020.09.009
[24]	Zhu, Q. and Xu, J.M. (2006) On Restricted Edge Connectivity and Extra Edge Connectivity of Hypercubes and Folded Hypercubes. Journal of University of Science and Technology of China, 36, 246-253.
[25]	Guo, L. and Guo, X. (2014) Fault Tolerance of Hypercubes and Folded Hypercubes. The Journal of Supercomputing, 68, 1235-1240. https://doi.org/10.1007/s11227-013-1078-5