The g-Component Connectivity of Some Networks

Ganghua Xie, Yinkui Li^*

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

DOI: 10.4236/ojapps.2023.1312189                

Abstract

In 2012, Hsu et al. generalized the classical connectivity of graph G and introduced the concept of g-component connectivity CKg (G) to measure the fault tolerance of networks. In this paper, we determine the g-component connectivity of some graphs, such as fan graph, helm graph, crown graph, Gear graph and the Mycielskian graph of star graph and complete bipartite graph.

Keywords

g-Component Connectivity, Mycielskian Graph, The Fault Tolerance of Networks

1. Introduction

Multiprocessor systems are always built according to a graph which called its interconnection network (network, for short). In a network, vertices to processors, and edges correspond to communicating links between pairs of vertices. Since failures of processors and links are inevitable in multiprocessor systems, fault tolerance is an important issue in interconnection networks. Fault tolerance of interconnection networks becomes an essential problem and has been widely studied, such as, structure connectivity and substructure connectivity of hypercubes, extra connectivity of bubble sort star graphs, g-extra conditional diagnosability of hierarchical cubic networks, g-good-neighbor connectivity of graphs, conditional connectivity of Cayley graphs generated by unicyclic graphs.

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 [1] [2] [3] , 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. [4] [5] and Xu et al. [6] 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. [7] determined the g-component connectivity of alternating group networks $A{N}_n$ when $g=\mathrm{3,4}$ . Ding et al. [8] dealt with the g-component (edge) connectivity of shuffle-cubes $S{Q}_n$ for small g. Recently, Li et al. [9] studied the relationship between extra connectivity and component connectivity of general networks, and Hao et al. [10] and Guo et al. [11] independently proposed the relationship between extra edge connectivity and component connectivity of regular networks in the literature. In this paper, we mainly discusses g-component connectivity of some graphs, such as fan graph, helm graph, crown graph, gear graph and the Mycielskian graph of star graph and complete bipartite graph.

All graphs considered in this paper are finite and simple. We refer to the book [12] 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. For $u\mathrm{,}v\subseteq V\left(G\right)$ , $N_G\left(v\right)=\left\{u\in V\left(G\right)\mathrm{<mo>\; :\; </mo>}uv\in E\left(G\right)\right\}$ , $d_G\left(v\right)=\left|N_G\left(v\right)\right|$ . 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)={\displaystyle {\cup }_{v\in S}{N}_G\left(v\right)\backslash S}$ .

2. Preliminary

Proposition 2.1. [13] If H is spanning subgraph of G, then $c{\kappa }_g\left(H\right)\le c{\kappa }_g\left(G\right)$ .

Proposition 2.2. [13] Let g be a non-negative integer and G be a connected graph with order n. If $c{\kappa }_g\left(G\right)\ne 0$ , then $2\le g\le n-1$ , $n-1\le e\left(G\right)\le \left(\begin{array}{c}n\\ 2\end{array}\right)-1$ .

Proposition 2.3. [13] Let g be a positive integer and G be a connected graph of order n such that $2\le g\le n-1$ . Then $\kappa \left(G\right)\le c{\kappa }_g\left(G\right)\le n-g$ . Particularly, when $\kappa \left(G\right)=1$ , $1\le c{\kappa }_g\left(G\right)\le n-g$ .

Proposition 2.4. [13] Let g be a positive integer. If $C_n$ is a cycle with order $n\left(n\ge 4\right)$ , then $c{\kappa }_g\left(G\right)=g$ for $2\le g\le \lfloor \frac{n}{2}\rfloor$ .

Proposition 2.5. [13] Let g be a positive integer. For the complete bipartite graph $K_{a\mathrm{,}b}\left(a\ge b\ge 2\right)$ , we have $g\le a$ and $c{\kappa }_g\left(K_{a\mathrm{,}b}\right)=b$ .

Proposition 2.6. [14] Let g be a positive integer and $P_n$ is a path with order $n\left(n\ge 3\right)$ , then $c{\kappa }_g\left(P_n\right)=g-1$ for $2\le g\le \lceil \frac{n}{2}\rceil$ .

3. Main Result

In this section, we determine the g-component connectivity of graphs such as fan graph, helm graph, crown graph, gear graph and the Mycielskian graph of star graph and complete bipartite graph.

Let $n\ge 3$ , the fan graph G (Figure 1) is defined as the join of $K_1$ and the path $P_n$ . Let $G=K_1+P_n$ . We call the vertex of $K_1$ the center of G.

Theorem 3.1. Let g be a positive integer and $G=K_1+P_n$ with $n\ge 3$ . If $2\le g\le \lceil \frac{n}{2}\rceil$ , then $c{\kappa }_g\left(G\right)=g$ .

Proof. Let v be the center of fan graph $G=K_1+P_n$ and $V\left(G\right)=\left\{v\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_n\right\}$ . Suppose X is a g-component cut of G, then $v\in X$ . If not, assume $v\notin X$ , then $\omega \left(G-X\right)=1$ , a contradiction. By Proposition 5, we know $c{\kappa }_g\left(P_n\right)=g-1$ and thus $P_n$ has a g-component cut $X_0$ such that $\omega \left(P_n-X_0\right)\ge g$ and $\left|X_0\right|=g-1$ . Let $X^{\prime }=X_0\cup \left\{v\right\}$ , it is clear that $X^{\prime }$ is a g-component cut of G since $\omega \left(G-X^{\prime }\right)=\omega \left(P_n-X_0\right)\ge g$ . Consider $\left|X^{\prime }\right|=\left|X_0\right|+1=g-1+1=g$ , we have $c{\kappa }_g\left(G\right)\le \left|X^{\prime }\right|=g$ .

On the other hand, we show $c{\kappa }_g\left(G\right)\ge g$ . If not, assume that there exit a g-component cut X of G such that $\left|X\right|\le g-1$ . Consider $v\in X$ , let $X_1=X-\left\{v\right\}$ , since $X_1$ is a cut of $P_n$ with $\left|X_1\right|\le g-2$ , we have $\omega \left(P_n-X_1\right)\le \left|X_1\right|+1\le g-1$ . This implies $\omega \left(G-X\right)=\omega \left(P_n-X_1\right)\le g-1$ , a contradiction. So we have $c{\kappa }_g\left(G\right)\ge g$ . Therefore, $c{\kappa }_g\left(G\right)=g$ . This completes the proof.

A wheel graph $W_n$ with order n, also called n-wheel, is a graph that contains a cycle of order n, and for which every vertex in the cycle is connected to one additional vertex. The helm graph is the graph on $2n+1$ vertices obtained from the n-wheel by adjoining a pendant edge at each vertex of the cycle.

Theorem 3.2. Let G be a helm graph with order $2n+1$ for $n\ge 3$ and g be a positive integer for $2\le g\le n+1$ . Then $c{\kappa }_g\left(G\right)=g-1$ .

Proof. Suppose $V\left(G\right)=\left\{v\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_n\right\}$ such that $d\left(u_i\right)=1$ for $1\le i\le n$ . First let $F_0=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{g-1}\right\}$ , it is clear that $G-F_0$ is disconnected with $\omega \left(G-F_0\right)=g$ . So we have $c{\kappa }_g\left(G\right)\le \left|F_0\right|=g-1$ . On the other hand, notices that $\omega \left(G-S\right)\le \left|S\right|+1$ for any cut set S of G, we have $\left|X\right|\ge \omega \left(G-X\right)-1$ for any g-cut X. This implies that $c{\kappa }_g\left(G\right)\ge g-1$ . Thus we get $c{\kappa }_g\left(G\right)=g-1$ . This completes the proof.

The Gear graph $G_n$ , also call a bipartite wheel graph, is obtained by subdividing each edge of the outer cycle of a wheel $W_n$ .

Figure 1. The fan graph $G=k_1+p_n$ .

Theorem 3.3. Let G be a Gear graph with $n\ge 2$ and g be a positive integer. If $2\le g\le n+1$ , then

$c{\kappa }_g\left(G\right)=(\begin{array}{ll}g,\hfill & 2\le g\le n-1;\hfill \\ n,\hfill & g=n,n+1.\hfill \end{array}$

Proof. Let $V\left(G\right)=V_1\cup V_2$ for $V_1=\left\{v\right\}\cup \left\{u_i\right\}$ and $V_2=\left\{v_i\right\}$ such that $d\left(u_i\right)=2$ for $1\le i\le n$ . Clearly, $V_1$ and $V_2$ are both independent set of G.

Case 1 $2\le g\le n-1$ .

Let $X_0=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_g\right\}$ . Clearly, $\left|X_0\right|=g$ and $\omega \left(G-X_0\right)=g$ . Thus we have $c{\kappa }_g\left(G\right)\le \left|X_0\right|=g$ . Now we show $c{\kappa }_g\left(G\right)\ge g$ . If not, assume there exist $S\subseteq V\left(G\right)$ is a g-component cut of G with $\left|S\right|\le g-1$ , then $v\notin S$ . In fact, if $v\in S$ , consider $G-v$ is a cycle $C_{2n}$ , then $S^{\prime }=S-\left\{v\right\}$ is a cut set of $C_{2n}$ with $\left|S^{\prime }\right|\le g-2$ . By Proposition 4, $C_{2n}-S^{\prime }$ has at most $g-2$ components and so does $G-S$ , the later contradicts to S is a g-component cut of G. Now we go on deducing contradictions. If $S\cap V_1\ne \varnothing$ , then either $\omega \left(G-S\right)=1$ or $\omega \left(G-S\right)\le g-1$ , a contradiction. If $S\cap V_1\ne \varnothing$ , then $\omega \left(G-S\right)\le g-1$ , a contradiction again. So we get $c{\kappa }_g\left(G\right)\ge g$ and thus $c{\kappa }_g\left(G\right)=g$ .

Case 2 $g=n\mathrm{,}n+1$ .

Let $X_1=V_2$ . Clearly, $\left|X_1\right|=n$ and $\omega \left(G-X_1\right)=n+1$ , thus we have $c{\kappa }_g\left(G\right)\le n$ . On the other hand, we show $c{\kappa }_g\left(G\right)\ge n$ . If not, assume S is a g-component cut of G with $\left|S\right|\le n-1$ . Consider $v\notin S$ , similarly as Case 1, we would get $c{\kappa }_g\left(G\right)\ge n$ . Hence $c{\kappa }_g\left(G\right)=n$ . This completes the proof.

For $n\ge 3$ , the n-crown graph on 2n vertices is defined as $K_{n\mathrm{,}n}-M$ , where M is a perfect matching in $K_{n\mathrm{,}n}$ . Crown graphs can also be viewed as the tensor product $K_{n\mathrm{,}n}\times K_2$ .

Theorem 3.4. Let G be a n-crown graph with $n\ge 3$ and g be a positive integer. If $2\le g\le n$ , then

$c{\kappa }_g\left(G\right)=(\begin{array}{ll}n-1,\hfill & g=2;\hfill \\ n,\hfill & 3\le g\le n.\hfill \end{array}$

Proof. Let $A=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ , $B=\left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_n\right\}$ be the set of two parts of the graph G with $d\left(v_i\right)=d\left(u_j\right)=n-1$ for $1\le i\le n\mathrm{,1}\le j\le n$ ).

Case 1 $g=2$ .

Take arbitrary vertex of A, named $v_1$ , consider $N_G\left(v_1\right)=\left\{u_2\mathrm{,}{u}_3\mathrm{,}\cdots \mathrm{,}{u}_n\right\}$ , let $S=N_G\left(v_1\right)$ , then $\omega \left(G-S\right)=2$ , this means $c{\kappa }_2\left(G\right)\le n-1$ .

Now, to show $c{\kappa }_2\left(G\right)\ge n-1$ . If not, assume there exit a 2-component cut S of G such that $\left|S\right|\le n-2$ , this contradicts to the fact that G is $\left(n-1\right)$ -regular. So, $c{\kappa }_2\left(G\right)\ge n-1$ . Hence, we get $c{\kappa }_2\left(G\right)=n-1$ .

Case 2 $3\le g\le n$ .

Let $F_0=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ , consider $G-F$ is disconnected and $\omega \left(G-F_0\right)=n$ , we get $c{\kappa }_g\left(G\right)\le n$ .

Now, show $c{\kappa }_g\left(G\right)\ge n$ . If not, assume that there exist is a g-component cut F of G such that $\left|F\right|\le n-1$ . Similarly, consider G is $\left(n-1\right)$ -regular, it is impossible to obtain a g-component cut F of G such that $\left|F\right|\le n-1$ . So, $c{\kappa }_g\left(G\right)\ge n$ and thus we get $c{\kappa }_g\left(G\right)=n$ . Hence, $c{\kappa }_g\left(K_{n\mathrm{,}n}-M\right)=n$

Next, we define the traditional Mycielski construction. Suppose G is a graph with $V\left(G\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ . The Mycielskian of G, denoted $\mu \left(G\right)$ , is a graph with vertex set $\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_n\mathrm{,}\omega \right\}$ . For each edge $v_i{v}_j$ in G, the graph $\mu \left(G\right)$ has $v_i{v}_j$ , $v_i{u}_j$ , and $u_i{v}_j$ . In addition, $\mu \left(G\right)$ has edges $u_i\omega$ for $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ . Clearly, $\mu \left(G\right)$ has an isomorphic copy of G on vertices $\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ . $\mu \left(K_{\mathrm{1,3}}\right)$ is show in Figure 2.

Facts: Let G be a graph with $\left|G\right|=n$ and $d_G\left(v_i\right)=k$ . Then $\left|\mu \left(G\right)\right|=2n+1$ ; $d_{\mu \left(G\right)}\left(\omega \right)=n$ ; $d_{\mu \left(G\right)}\left(v_i\right)=2k$ ; $d_{\mu \left(G\right)}\left(u_i\right)=2k$ ; $N_{\mu \left(G\right)}\left(u_i\right)\backslash \left\{\omega \right\}=N_G\left(v_i\right)$ .

Theorem 3.5. Let $S_n$ (Figure 3) be a star graph with order $n\ge 2$ and g be a positive integer. 1) If $n=2$ , then $c{\kappa }_2\left(\mu \left(S_2\right)\right)=2$ ; 2) If $n\ge 3$ , then

$c{\kappa }_g\left(\mu \left(S_n\right)\right)=(\begin{array}{ll}2,\hfill & 2\le g\le n;\hfill \\ 3,\hfill & n+1\le g\le 2\left(n-1\right).\hfill \end{array}$

Proof.

Case 1 $n=2$ .

Figure 2. $\mu \left(K_{\mathrm{1,3}}\right)$ .

Figure 3. The graph $\mu \left(S_n\right)$ .

Clearly, $\mu \left(S_2\right)$ is a 5-circle, then by Proposition 2.4, we get $c{\kappa }_2\left(\mu \left(S_2\right)\right)=2$ .

Case 2 $n\ge 3$ .

Subcase 1 $2\le g\le n$

Let $F=\left\{v_n\mathrm{,}\omega \right\}$ , consider $\omega \left(\mu \left(S_n\right)-F\right)=n\ge g$ . We get $c{\kappa }_g\left(\mu \left(S_n\right)\right)\le 2$ .

Now, show $c{\kappa }_g\left(\mu \left(S_n\right)\right)\ge 2$ . On the contrary, suppose F is a vertex set of $\mu \left(S_n\right)$ such that $\left|F\right|=1$ and $\mu \left(S_n\right)-F$ has at least g components. Then discuss as follows.

If $F=\left\{u_n\right\}$ or $\left\{v_n\right\}$ or $\left\{\omega \right\}$ , then $\omega \left(\mu \left(S_n\right)-F\right)=1<g$ , a contradiction. If $\left|F\cap \left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\right\}\right|=1$ , since $\omega \left(\mu \left(S_n\right)-F\right)=1$ , then $\mu \left(S_n\right)-F$ is connected, a contradiction. If $\left|F\cap \left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_{n-1}\right\}\right|=1$ , then $\omega \left(\mu \left(S_n\right)-F\right)=1$ , that $\mu \left(S_n\right)-F$ is connected, also contradiction. Hence, $c{\kappa }_g\left(\mu \left(S_n\right)\right)=2$ .

Subcase 2 $n+1\le g\le 2\left(n-1\right)$

First let $X=\left\{v_n\mathrm{,}{u}_n\mathrm{,}\omega \right\}$ . Clearly, $\left|X\right|=3$ and $\omega \left(\mu \left(S_n\right)-X\right)=2\left(n-1\right)\ge g$ . So $c{\kappa }_g\left(\mu \left(S_n\right)\right)\le 3$ .

Now show $c{\kappa }_g\left(\mu \left(S_n\right)\right)\ge 3$ . On the contrary, suppose that S is a g-component cut of G with $\left|S\right|\le 2$ . Let $v\in \left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{n-1}\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_{n-1}\right\}$ , we deduce contradictions as follows.

If $S=\left\{v_n\mathrm{,}{u}_n\right\}$ or $\left\{v_n\mathrm{,}\omega \right\}$ , then $\omega \left(\mu \left(S_n\right)-S\right)=n\le g-1$ , a contradiction. If $S=\left\{u_n\mathrm{,}\omega \right\}$ or $\left\{u_n\mathrm{,}v\right\}$ or $\left\{u_n\mathrm{,}v\right\}$ or $\left\{v\mathrm{,}\omega \right\}$ , then $\omega \left(\mu \left(S_n\right)-S\right)=1<g$ , a contradiction. Hence, $c{\kappa }_g\left(\mu \left(S_n\right)\right)=3$ .

Theorem 3.6. Let $K_{n\mathrm{,}m}$ be a complete bipartite graph with $m\ge n\ge 2$ and g be a positive integer. Then

$c{\kappa }_g\left(\mu \left(K_{n,m}\right)\right)=(\begin{array}{ll}n+1,\hfill & 2\le g\le m+1;\hfill \\ 2n+1,\hfill & m+2\le g\le 2m.\hfill \end{array}$

Proof. Let $X=\left\{v_{m+1}\mathrm{,}{v}_{m+2}\mathrm{,}\cdots \mathrm{,}{v}_{m+n}\right\}$ , $Y=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_m\right\}$ be two parts of complete bipartite graph $K_{n\mathrm{,}m}$ , $S=\left\{u_{m+1}\mathrm{,}{u}_{m+2}\mathrm{,}\cdots \mathrm{,}{u}_{m+n}\right\}$ , $T=\left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_m\right\}$ . $G_1=G\left[S\cup Y\right]$ , $G_2=G\left[X\cup T\right]$ and $G_3=G-\left\{\omega \right\}$ . By proposition 2.6, we have $c{\kappa }_{g^{\prime }}\left(G_1\right)=c{\kappa }_{g^{\prime }}\left(G_2\right)=n$ for $g^{\prime }\le m$ .

Case 1 $2\le g\le m+1$ .

Let $F_0=X\cup \left\{\omega \right\}=\left\{v_{m+1}\mathrm{,}{v}_{m+2}\mathrm{,}\cdots \mathrm{,}{v}_{m+n}\mathrm{,}\omega \right\}$ . Clearly, $\left|F_0\right|=n+1$ and $\omega \left(\mu \left(K_{n\mathrm{,}m}\right)-F_0\right)=m+1\ge g$ . Hence, $c{\kappa }_g\left(\mu \left(K_{n\mathrm{,}m}\right)\right)\le n+1$ .

On the other hand, we show $c{\kappa }_g\left(\mu \left(K_{n\mathrm{,}m}\right)\right)\ge n+1$ . If not, assume there exist $F\subseteq V\left(\mu \left(K_{n\mathrm{,}m}\right)\right)$ is a g-component cut of $\mu \left(K_{n\mathrm{,}m}\right)$ with $\left|F\right|\le n$ , then we distinguish cases to deduce contradictions.

Subcase 1.1 $\omega \in F$ .

Let $F_0=F-\left\{\omega \right\}$ , $F_1=F_0\cap V\left(G_1\right)$ and $F_2=F_0\cap V\left(G_2\right)$ , so $\left|F_0\right|\le n-1$ . If $F_0\subseteq V\left(G_1\right)$ , then $F_0$ is a cut of $G_1$ with $\left|F_0\right|\le n-1<n$ , we have $\omega \left(G_1-F_0\right)=1$ , then it is connected between $G_1-F_0$ and $G_2$ , so $\omega \left(\mu \left(K_{n,m}\right)-F\right)=1<g$ , a contradiction. If $F_0\subseteq V\left(G_2\right)$ , the reason is similar to that of the situation “ $F_0\subseteq V\left(G_1\right)$ ”. If $F_1\ne \varnothing$ and $F_0\ne \varnothing$ , then $\omega \left(G_1-F_1\right)=1$ and $\omega \left(G_2-F_2\right)=1$ , and it is connected between $G_1-F_1$ and $G_2-F_2$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=1<g$ , also a contradiction.

Subcase 1.2 $\omega \notin F$ .

Let $F_1=F\cap V\left(G_1\right)$ and $F_2=F\cap V\left(G_2\right)$ . If $\left|F_1\right|=\left|F\right|\le n$ , then we have $\omega \left(G_1-F_1\right)=m$ or 1, however $G_1-F_1$ , $G_2$ and $\omega$ are connected, this implies that $\omega \left(\mu \left(K_{n,m}\right)-F\right)=1<g$ , a contradiction. If $\left|F_2\right|=\left|F\right|\le n$ , the reason is similar to that of the situation “ $\left|F_1\right|=\left|F\right|\le n$ ”. If $F_1\ne \varnothing$ and $F_0\ne \varnothing$ , then $\left|F_1\right|\le n-1$ and $\left|F_2\right|\le n-1$ , this implies that $\omega \left(G_1-F_1\right)=1$ and $\omega \left(G_2-F_2\right)=1$ , then $G_1-F_1$ , $G_2-F_2$ and $\omega$ are connected, this implies that $\omega \left(\mu \left(K_{n,m}\right)-F\right)=1<g$ , a contradiction. Hence, $c{\kappa }_g\left(\mu \left(K_{n\mathrm{,}m}\right)\right)=n+1$ .

Case 2 $m+2\le g\le 2m$ .

Let $F=X\cup S\cup \left\{\omega \right\}=\left\{v_{m+1}\mathrm{,}{v}_{m+2}\mathrm{,}\cdots \mathrm{,}{v}_{m+n}\mathrm{,}{u}_{m+1}\mathrm{,}{u}_{m+2}\mathrm{,}\cdots \mathrm{,}{u}_{m+n}\mathrm{,}\omega \right\}$ . Clearly, $\left|F\right|=2n+1$ and $\omega \left(\mu \left(K_{n\mathrm{,}m}\right)-F\right)=2m\ge g$ . So $c{\kappa }_g\left(\mu \left(K_{n\mathrm{,}m}\right)\right)\le 2n+1$ .

Now, to show $c{\kappa }_g\left(\mu \left(K_{n\mathrm{,}m}\right)\right)\ge 2n+1$ . Suppose, to the contrary, that $F\subseteq V\left(\mu \left(K_{n\mathrm{,}m}\right)\right)$ is a vertex set of $\mu \left(K_{n\mathrm{,}m}\right)$ such that $\left|F\right|\le 2n$ and $\mu \left(K_{n\mathrm{,}m}-F\right)$ has at least g components. Let $F_1=F\cap V\left(G_1\right)$ and $F_2=F\cap V\left(G_2\right)$ .

Subcase 2.1 $n+1\le m\le 2n-1$ .

If $F=F_1\cup \omega$ , then $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_1\right)\le n+1<g$ between $G_1-F_1$ and $G_2$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1\right)\le n+1<g$ , a contradiction. If $F=F_2\cup \omega$ , then $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_2\right)\le m+1<g$ between $G_2-F_2$ and $G_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_2\right)\le m+1<g$ , a contradiction. If $F=F_1\cup F_2\cup \omega$ , assume $\left|F_1\right|\le \left|F_2\right|$ , since $\left|F_1\right|+\left|F_2\right|\le 2n-1$ , then $\left|F_1\right|\le n-1$ , we have $\omega \left(G_1-F_1\right)=1$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_1-F_2\right)\le m+1<g$ between $G_2-F_2$ and $G_1-F_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)\le m+1<g$ , a contradiction; assume $\left|F_1\right|\ge \left|F_2\right|$ , since $\left|F_1\right|+\left|F_2\right|\le 2n-1$ , then $\left|F_2\right|\le n-1$ , we have $\omega \left(G_2-F_2\right)=1$ , $G_1-F_1$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_1-F_2\right)\le n+1<g$ between $G_2-F_2$ and $G_1-F_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)\le n+1<g$ , a contradiction. If $F=F_1\cup F_2$ , assume $\left|F_1\right|=\left|F_2\right|=n$ , we have $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected or disconnected and $\omega \left(G-F_1-F_2\right)\le m+1<g$ , thus $\omega \left(G-F\right)=\omega \left(G-F_1-F_2\right)\le m+1<g$ , a contradiction; assume $\left|F_1\right|<\left|F_2\right|$ , then $\left|F_1\right|\le n-1$ , we have $\omega \left(G_1-F_1\right)=1$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , however $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected, thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction; assume $\left|F_1\right|>\left|F_2\right|$ , then $\left|F_2\right|\le n-1$ , we have $\omega \left(G_2-F_2\right)=1$ , $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , however $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected, thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction. If $\left|F_1\right|=\left|F\right|\le 2n$ , then we have $\omega \left(G_1-F_1\right)\le m$ , however $G_1-F_1$ , $G_2$ and $\omega$ are connected, this implies that $\omega \left(\mu \left(K_{n,m}\right)-F\right)=1<g$ , a contradiction. If $\left|F_2\right|=\left|F\right|\le 2n$ , the reason is similar to that of the situation “ $\left|F_1\right|=\left|F\right|\le 2n$ ”.

Subcase 2.2 $m=2n$ .

If $F=F_1\cup \omega$ , then $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , then it is connected between $G_1-F_1$ and $G_2$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1\right)=1<g$ , a contradiction. If $F=F_2\cup \omega$ , then $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_2\right)\le m+1<g$ between $G_2-F_2$ and $G_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_2\right)\le m+1<g$ , a contradiction. If $F=F_1\cup F_2\cup \omega$ , assume $\left|F_1\right|\le \left|F_2\right|$ , since $\left|F_1\right|+\left|F_2\right|\le 2n-1$ , then $\left|F_1\right|\le n-1$ , we have $\omega \left(G_1-F_1\right)=1$ , $G_1-F_1$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_1-F_2\right)\le m+1<g$ between $G_2-F_2$ and $G_1-F_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)\le m+1<g$ , a contradiction; assume $\left|F_1\right|\ge \left|F_2\right|$ , since $\left|F_1\right|+\left|F_2\right|\le 2n-1$ , then $\left|F_2\right|\le n-1$ , we have $\omega \left(G_2-F_2\right)=1$ , $G_1-F_1$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected between $G_2-F_2$ and $G_1-F_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction. If $F=F_1\cup F_2$ , assume $\left|F_1\right|=\left|F_2\right|=n$ , we have $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected or disconnected and $\omega \left(G-F_1-F_2\right)\le m+1<g$ , thus $\omega \left(G-F\right)=\omega \left(G-F_1-F_2\right)\le m+1<g$ , a contradiction; assume $\left|F_1\right|<\left|F_2\right|$ , then $\left|F_1\right|\le n-1$ , we have $\omega \left(G_1-F_1\right)=1$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , however $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected, thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction; assume $\left|F_1\right|>\left|F_2\right|$ , then $\left|F_2\right|\le n-1$ , we have $\omega \left(G_2-F_2\right)=1$ , $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , however $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected, thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction. If $\left|F_1\right|=\left|F\right|\le 2n$ , then we have $\omega \left(G_1-F_1\right)\le m$ , however $G_1-F_1$ , $G_2$ and $\omega$ are connected, this implies that $\omega \left(\mu \left(K_{n,m}\right)-F\right)=1<g$ , a contradiction. If $\left|F_2\right|=\left|F\right|\le 2n$ , the reason is similar to that of the situation “ $\left|F_1\right|=\left|F\right|\le 2n$ ”.

Subcase 2.3 $m>2n$ .

If $F=F_1\cup \omega$ , then $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , then it is connected between $G_1-F_1$ and $G_2$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1\right)=1<g$ , a contradiction. If $F=F_2\cup \omega$ , then $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_2\right)\le m+1<g$ between $G_2-F_2$ and $G_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_2\right)\le m+1<g$ , a contradiction. If $F=F_1\cup F_2\cup \omega$ , assume $\left|F_1\right|\le \left|F_2\right|$ , since $\left|F_1\right|+\left|F_2\right|\le 2n-1$ , then $\left|F_1\right|\le n-1$ , we have $\omega \left(G_1-F_1\right)=1$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected or disconnected and $\omega \left(G_3-F_1-F_2\right)\le m+1<g$ between $G_2-F_2$ and $G_1-F_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)\le m+1<g$ , a contradiction; assume $\left|F_1\right|\ge \left|F_2\right|$ , since $\left|F_1\right|+\left|F_2\right|\le 2n-1$ , then $\left|F_2\right|\le n-1$ , we have $\omega \left(G_2-F_2\right)=1$ , $G_1-F_1$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then it is connected between $G_2-F_2$ and $G_1-F_1$ , thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction. If $F=F_1\cup F_2$ , assume $\left|F_1\right|=\left|F_2\right|=n$ , we have $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , then $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected or disconnected and $\omega \left(G-F_1-F_2\right)\le m+1<g$ , thus $\omega \left(G-F\right)=\omega \left(G-F_1-F_2\right)\le m+1<g$ , a contradiction; assume $\left|F_1\right|<\left|F_2\right|$ , then $\left|F_1\right|\le n-1$ , we have $\omega \left(G_1-F_1\right)=1$ , $G_2-F_2$ is connected or disconnected and $\omega \left(G_2-F_2\right)\le m$ , however $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected, thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction; assume $\left|F_1\right|>\left|F_2\right|$ , then $\left|F_2\right|\le n-1$ , we have $\omega \left(G_2-F_2\right)=1$ , $G_1-F_1$ is connected or disconnected and $\omega \left(G_1-F_1\right)\le m$ , however $G_2-F_2$ , $G_1-F_1$ and $\omega$ is connected, thus $\omega \left(\mu \left(K_{n,m}\right)-F\right)=\omega \left(G_3-F_1-F_2\right)=1<g$ , a contradiction. If $\left|F_1\right|=\left|F\right|\le 2n$ , then we have $\omega \left(G_1-F_1\right)\le m$ , however $G_1-F_1$ , $G_2$ and $\omega$ are connected, this implies that $\omega \left(\mu \left(K_{n,m}\right)-F\right)=1<g$ , a contradiction. If $\left|F_2\right|=\left|F\right|\le 2n$ , the reason is similar to that of the situation “ $\left|F_1\right|=\left|F\right|\le 2n$ ”. Hence, $c{\kappa }_g\left(\mu \left(K_{n\mathrm{,}m}\right)\right)=2n+1$ .

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 (07M2022007).

Conflicts of Interest

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

References

[1]	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
[2]	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
[3]	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
[4]	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
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, London. https://doi.org/10.1007/978-1-349-03521-2
[13]	Li, H., Zhang, S., Ye, C., et al. (2021) The g-Component Connectivity of Graphs. Theoretical Computer Science, 889, 96-104. https://doi.org/10.1016/j.tcs.2021.07.039
[14]	Day, D.P., Oellermann, O.R. and Swart, H.C. (1999) Bounds on the Size of Graphs of Given Order and l-Connectivity. Discrete Mathematics, 197, 217-223. https://doi.org/10.1016/S0012-365X(99)90067-5