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
such that
has at least
components. The g-component connectivity of graph G, denoted by
, is the cardinality of a minimum g-component cut of graph G, that is,
. Of course, we define that
if G is a complete graph
or a disconnected graph. Obviously,
and
.
In [1] [2] [3] , authors determined the g-component connectivity of n-dimensional bubble-sort star graph
, n-dimensional burnt pancake graph
, the hierarchical star networks
, the alternating Group graphs
and split star graph
. 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
, n-dimensional dual cube
and transposition tree. In addition, Chang et al. [7] determined the g-component connectivity of alternating group networks
when
. Ding et al. [8] dealt with the g-component (edge) connectivity of shuffle-cubes
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
,
,
, and
represent respectively the size, the order, the complement and the number of components of G. For
,
,
. We call G k-regular if
for every vertex
. By
and
denote the minimum and maximum degree of the graph G, respectively. By
denote the number of elements in S and
denote the set of vertices of G which has neighbour vertex in S, that means
.
2. Preliminary
Proposition 2.1. [13] If H is spanning subgraph of G, then
.
Proposition 2.2. [13] Let g be a non-negative integer and G be a connected graph with order n. If
, then
,
.
Proposition 2.3. [13] Let g be a positive integer and G be a connected graph of order n such that
. Then
. Particularly, when
,
.
Proposition 2.4. [13] Let g be a positive integer. If
is a cycle with order
, then
for
.
Proposition 2.5. [13] Let g be a positive integer. For the complete bipartite graph
, we have
and
.
Proposition 2.6. [14] Let g be a positive integer and
is a path with order
, then
for
.
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
, the fan graph G (Figure 1) is defined as the join of
and the path
. Let
. We call the vertex of
the center of G.
Theorem 3.1. Let g be a positive integer and
with
. If
, then
.
Proof. Let v be the center of fan graph
and
. Suppose X is a g-component cut of G, then
. If not, assume
, then
, a contradiction. By Proposition 5, we know
and thus
has a g-component cut
such that
and
. Let
, it is clear that
is a g-component cut of G since
. Consider
, we have
.
On the other hand, we show
. If not, assume that there exit a g-component cut X of G such that
. Consider
, let
, since
is a cut of
with
, we have
. This implies
, a contradiction. So we have
. Therefore,
. This completes the proof.
A wheel graph
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
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
for
and g be a positive integer for
. Then
.
Proof. Suppose
such that
for
. First let
, it is clear that
is disconnected with
. So we have
. On the other hand, notices that
for any cut set S of G, we have
for any g-cut X. This implies that
. Thus we get
. This completes the proof.
The Gear graph
, also call a bipartite wheel graph, is obtained by subdividing each edge of the outer cycle of a wheel
.
Theorem 3.3. Let G be a Gear graph with
and g be a positive integer. If
, then
Proof. Let
for
and
such that
for
. Clearly,
and
are both independent set of G.
Case 1
.
Let
. Clearly,
and
. Thus we have
. Now we show
. If not, assume there exist
is a g-component cut of G with
, then
. In fact, if
, consider
is a cycle
, then
is a cut set of
with
. By Proposition 4,
has at most
components and so does
, the later contradicts to S is a g-component cut of G. Now we go on deducing contradictions. If
, then either
or
, a contradiction. If
, then
, a contradiction again. So we get
and thus
.
Case 2
.
Let
. Clearly,
and
, thus we have
. On the other hand, we show
. If not, assume S is a g-component cut of G with
. Consider
, similarly as Case 1, we would get
. Hence
. This completes the proof.
For
, the n-crown graph on 2n vertices is defined as
, where M is a perfect matching in
. Crown graphs can also be viewed as the tensor product
.
Theorem 3.4. Let G be a n-crown graph with
and g be a positive integer. If
, then
Proof. Let
,
be the set of two parts of the graph G with
for
).
Case 1
.
Take arbitrary vertex of A, named
, consider
, let
, then
, this means
.
Now, to show
. If not, assume there exit a 2-component cut S of G such that
, this contradicts to the fact that G is
-regular. So,
. Hence, we get
.
Case 2
.
Let
, consider
is disconnected and
, we get
.
Now, show
. If not, assume that there exist is a g-component cut F of G such that
. Similarly, consider G is
-regular, it is impossible to obtain a g-component cut F of G such that
. So,
and thus we get
. Hence,
Next, we define the traditional Mycielski construction. Suppose G is a graph with
. The Mycielskian of G, denoted
, is a graph with vertex set
. For each edge
in G, the graph
has
,
, and
. In addition,
has edges
for
. Clearly,
has an isomorphic copy of G on vertices
.
is show in Figure 2.
Facts: Let G be a graph with
and
. Then
;
;
;
;
.
Theorem 3.5. Let
(Figure 3) be a star graph with order
and g be a positive integer. 1) If
, then
; 2) If
, then
Proof.
Case 1
.
Clearly,
is a 5-circle, then by Proposition 2.4, we get
.
Case 2
.
Subcase 1
Let
, consider
. We get
.
Now, show
. On the contrary, suppose F is a vertex set of
such that
and
has at least g components. Then discuss as follows.
If
or
or
, then
, a contradiction. If
, since
, then
is connected, a contradiction. If
, then
, that
is connected, also contradiction. Hence,
.
Subcase 2
First let
. Clearly,
and
. So
.
Now show
. On the contrary, suppose that S is a g-component cut of G with
. Let
, we deduce contradictions as follows.
If
or
, then
, a contradiction. If
or
or
or
, then
, a contradiction. Hence,
.
Theorem 3.6. Let
be a complete bipartite graph with
and g be a positive integer. Then
Proof. Let
,
be two parts of complete bipartite graph
,
,
.
,
and
. By proposition 2.6, we have
for
.
Case 1
.
Let
. Clearly,
and
. Hence,
.
On the other hand, we show
. If not, assume there exist
is a g-component cut of
with
, then we distinguish cases to deduce contradictions.
Subcase 1.1
.
Let
,
and
, so
. If
, then
is a cut of
with
, we have
, then it is connected between
and
, so
, a contradiction. If
, the reason is similar to that of the situation “
”. If
and
, then
and
, and it is connected between
and
, thus
, also a contradiction.
Subcase 1.2
.
Let
and
. If
, then we have
or 1, however
,
and
are connected, this implies that
, a contradiction. If
, the reason is similar to that of the situation “
”. If
and
, then
and
, this implies that
and
, then
,
and
are connected, this implies that
, a contradiction. Hence,
.
Case 2
.
Let
. Clearly,
and
. So
.
Now, to show
. Suppose, to the contrary, that
is a vertex set of
such that
and
has at least g components. Let
and
.
Subcase 2.1
.
If
, then
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction. If
, then
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction. If
, assume
, since
, then
, we have
,
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction; assume
, since
, then
, we have
,
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction. If
, assume
, we have
is connected or disconnected and
,
is connected or disconnected and
, then
,
and
is connected or disconnected and
, thus
, a contradiction; assume
, then
, we have
,
is connected or disconnected and
, however
,
and
is connected, thus
, a contradiction; assume
, then
, we have
,
is connected or disconnected and
, however
,
and
is connected, thus
, a contradiction. If
, then we have
, however
,
and
are connected, this implies that
, a contradiction. If
, the reason is similar to that of the situation “
”.
Subcase 2.2
.
If
, then
is connected or disconnected and
, then it is connected between
and
, thus
, a contradiction. If
, then
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction. If
, assume
, since
, then
, we have
,
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction; assume
, since
, then
, we have
,
is connected or disconnected and
, then it is connected between
and
, thus
, a contradiction. If
, assume
, we have
is connected or disconnected and
,
is connected or disconnected and
, then
,
and
is connected or disconnected and
, thus
, a contradiction; assume
, then
, we have
,
is connected or disconnected and
, however
,
and
is connected, thus
, a contradiction; assume
, then
, we have
,
is connected or disconnected and
, however
,
and
is connected, thus
, a contradiction. If
, then we have
, however
,
and
are connected, this implies that
, a contradiction. If
, the reason is similar to that of the situation “
”.
Subcase 2.3
.
If
, then
is connected or disconnected and
, then it is connected between
and
, thus
, a contradiction. If
, then
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction. If
, assume
, since
, then
, we have
,
is connected or disconnected and
, then it is connected or disconnected and
between
and
, thus
, a contradiction; assume
, since
, then
, we have
,
is connected or disconnected and
, then it is connected between
and
, thus
, a contradiction. If
, assume
, we have
is connected or disconnected and
,
is connected or disconnected and
, then
,
and
is connected or disconnected and
, thus
, a contradiction; assume
, then
, we have
,
is connected or disconnected and
, however
,
and
is connected, thus
, a contradiction; assume
, then
, we have
,
is connected or disconnected and
, however
,
and
is connected, thus
, a contradiction. If
, then we have
, however
,
and
are connected, this implies that
, a contradiction. If
, the reason is similar to that of the situation “
”. Hence,
.
Acknowledgements
This paper Supported by AFSFQH (2022-ZJ-753), which mainly studies the fault tolerance of operation graph and Mycielskin graph
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
is discussed. Thirdly, the 5-component connectivity of the shuffled cube
and the twisted cube
is discussed.
Funding
Innovative Project (07M2022007).