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
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
that make
disconnected. The cardinality of the smallest vertex-cut set of a graph G is called the connectivity of the graph G, denoted by
. 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
. 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
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 [5] [6] [7] , 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. [8] [9] and Xu et al. [10] 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. [11] determined the g-component connectivity of alternating group networks
when
. Ding et al. [12] dealt with the g-component (edge) connectivity of shuffle-cubes
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
,
,
, and
represent respectively the size, the order, the complement and the number of components of G. Let
be a connected graph,
the neighbors of a vertex v in G (simply
),
the edges incident to v. For
, denote by
the set of edges of G with one end in X and tie other in Y. 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
Definition 1 [17] The n-dimensional hypercube is a connected graph with
vertices and denoted by
. The vertex set
or
. Two vertices
and
in
are adjacent if and only they differ in exact one position.
Definition 2 [18] The n-dimensional varietal hypercube, denoted by
, has
vertices, each labeled by an n-bit binary string and
or
.
is a complete graph
of two vertices labeled with 0 and 1, respectively. For
,
can be recursively constructed from two copies of
, denoted by
and
, and by adding
edges between
and
, where
or
,
or
. The vertex
is adjacent to the vertex
if and only if
1)
if
, or;
2)
and
if
.
Obviously,
is an n-regular and its girth is 4. Moreover, it contains circles of length 5 when
[19] [20] . The varietal hypercube
,
,
are illustrated in Figure 1.
From the definition, we can see that each vertex of
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,
can be obtained by adding a perfect matching M between
and
. Hence
can be viewed as
or
briefly. For any vertex
,
is the esge incident to u in M.
As a variant of the hypercube, the n-dimensional varietal hypercube
, which has the same number of vertices and edges as
, not only has the most ideal characteristics of
, including some characteristics such as recursive structure, strong connectivity, and symmetry but also has a smaller diameter than
, and its average distance is smaller than the hypercube [18] .
Proposition 1 [18]
for
.
Proposition 2 [21] [22] [23]
is a vertex-transitive and edge-transitive.
Proposition 3 [19]
for
.
Proposition 4 [24] Any two vertices of
have exactly two common neighbors for
if they have any.
Proposition 5 [25] Let x and y be any two vertices of
such that have two common neighbors.
Figure 1. The varietal hypercube
,
,
, and
.
1) If
,
, then the one common neighbor is in
, and the other one is in
.
2) If
or
, then the two common neighbors are in
or
.
3. Main Result
The varietal hypercube
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
have at most two common neighbors for
if they have.
Corollary 2. For any two vertices
,
1) if
, then they have at most two common neighbors;
2) if
, then they do not have common neighbors.
According to the definition of
, if any two vertices of
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
such that have only two common neighbors.
1) If
,
, then the one common neighbor is in
, and the other one is in
.
2) If
or
, then the two common neighbors are in
or
.
By the definition of
and above results, we have:
Theorem 4. If any two vertices of
have only one common neighbor, then the two vertices and their common neighbor are in some
.
In [19] , Xu et al., proved that
is super-λ and super-κ. Here, we present another proof of this result.
Theorem 5.
is super-λ for
.
By induction. It is true
. Let
. Assume that it holds for
.We will show that it is true for
.
Let
,
and
be not connected. Furthermore,
has only two connected components. Without loss of generality, suppose
. Then
is connected.
Note that
(
). If
is connected, then
is connected, a contradiction.
Assume that
is not connected. We have
. If
, then
and
. And each vertex of
has one neighbor in
, that is,
is connected, a contradiction.
Hence
. According to the inductive hypothesis,
is super-λ. Suppose the isolated vertex x and
are the only two components of
. And
is connected to
. If
, then
is connected, a contradiction. So
. We have
and
has only two components, one component ia x. Hence
is super-λ.
Theorem 6.
is super-κ for
.
The proof is similar to Theorem 5.
Theorem 7.
for
.
By definition of
, we have
, and we have
for
by proposition 3, thus
for
.
Theorem 8.
for
.
We choose two nonadjacent vertices x, y in a cycle
which has two common neighbors. Then
has at least three connected components and
. That is
.
We will show
by induction. It is easy to check that it is true for
. So we suppose
. Suppose it is true for
. Let
.
Let
with
. And
has at least three connected components, say,
,
,
. We have
or
. Without loss of generality, we set
. Hence
is connected.
If
has at least three components, from the inductive hypothesis, then
and
. Because each vertex of
has one neighbor in
, at most one vertex of
has no neighbors in
. So
has at most two connected components, a contradiction.
Hence
has at most two components. At most one component of
is not connected to
. And
has at most two connected components, a contradiction.
Theorem 9.
for
.
By definition of
, we have
, and we have
for
by proposition 3, thus
for
.
Theorem 10.
for
.
Take an edge
, then
. And
has at least three connected components. That is
.
Next we will show that
by induction. It is easy to check it is true for
. So we suppose
. Suppose it is true for all
. We will prove that is true for
.
Let
with
, and
has at least three components. Now since
, we have
or
, say,
. Since
, we have two cases.
Case 1
is not connected.
Then
and
has only two components.
If
is not connected, then
. That is
. But each vertex of
is connected to one component of
. Hence
has only two components, a contradiction.
Note that
(
). If
is connected, then
is connected to one component of
. Hence
has only two components, a contradiction.
Case 2
is connected.
If
is connected, then we are done. We assume that
is not connected. And
has at most one isolated vertex since
.
If
has at least three components, from the inductive hypothesis, then
. Hence at most one of components of
is not connected to
,
has at most two components, a contradiction.
Therefore we assume that
has only two components. But
(
),
has at most two components, a contradiction.
Theorem 11.
for
.
Take a path
. Then
. And
has at least four connected components. That is
.
Next we will show that
by induction. It is easy to check it is true for
. So we suppose
. Suppose it is true for all
. We will prove that is true for
.
Let
with
, and
has at least four components. Now since
, we have
or
, say,
. Since
(
),
has at most two components.
Case 1
is connected.
If
has at least four components, then
by the inductive hypothesis. We need delete at most two edges again. Since each vertex of
has a neighbor in
and
(
),
has at most three components, a contradiction.
Suppose
has at most three components. Because of
(
),
has at most three components, a contradiction.
Case 2
has only two connected components.
Then
and
. Note that
.
If
has at least three components, then
and
. But
and
(
),
has at most three components, a contradiction.
Hence
has at most two components. We have
, and
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
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 (07M2023004).