1. Introduction
The stability of a communication network, composed of processing nodes and communication links, is of prime importance to network designers. Many graph theoretical parameters have been used in measuring the vulnerability of networks, such as connectivity [1] [2], scattering number [3], tenacity [4], toughness [5] [6] and the rupture degree [7].
A hypergraph is a generalization of a graph in which an edge can join any number of vertices. For a hypergraph
,
is a set of elements called vertices, and
is a set of nonempty subset of V called edges. If
for
, we call H a k-uniform hypergraph. Clearly, ordinary graphs are referred as 2-uniform hypergraphs. A vertex
is said to be incident to an edge
if
. Two vertices are said to be adjacent if they are contained in one edge. And two edges are said to be adjacent if their intersection is not empty.
A k-uniform linear hypergraph is a k-uniform hypergraph such that every two edges have at most one common vertex. In this paper, all k-uniform hypergraphs are referred as k-uniform linear hypergraph that each edge has at most two non-1-degree vertices. For a vertex
, its degree
is the number of edges that contain
.
For an ordinary graph
and an integer
, the k-uniform hypergraph
underlies graph G, denoted by
, whose vertex set
and edge set
Hypergraphs are often used as a model of communication networks, paper index data, etc. The vulnerability of hypergraph is an important topic in graph theory research. Here we employ the rupture degree to measure the vulnerability of hypergraph
. The rupture degree
is similarly defined as
where
is a cut set (or destruction strategy) of
,
and
denote the number of components and the order of a largest component in
, respectively. A vertex cut set (or a destruction strategy) X of hypergraph
is called r-set (or the optimal destruction strategy) if
.
Although this vulnerability parameter of
is similar in form as the rupture degree of graph G, the optimal destruction strategy is different between G and
. For a tree T and hypergraph
in Figure 1, the cut sets
and
are the optimal destruction strategy of T and
, respectively.
Figure 1. The optimal destruction strategies for trees T and T4.
In this paper, we determine the rupture degree for some k-uniform hypergraphs such as k-uniform hypercomet
, k-uniform hypercycles
, k-uniform hypercomplete
and complete t-partite k-uniform hypergraph
.
Throughout this paper, we use
for the largest integer not large than x and
for the smallest integer not smaller than x. A comet
is a graph obtained by identifying one end of the path
with the center of the star
and the center is called the center of the comet. Any undefined terminology and notations can be found in [8] [9].
2. The Rupture Degree of Some k-Uniform Linear Hypergraphs
In this section, we will determine the rupture degree of some k-uniform hypergraphs such as k-uniform hypercomet
, k-uniform hypercycles
, k-uniform hyper complete
and complete t-partite k-uniform hypergraph
.
Lemma 2.1. Let X be an r-set of k-uniform hypergraph
. Then
.
If not, assume that
, then
. Suppose
for
are connected components of
satisfying
. Now select
and let
for
. Clearly,
and
. Thus we get
This contradicts to the choice of X. So
.n
Theorem 2.2. Let
be k-uniform hypergraph that underlies comet graph
. Then
Proof. We distinguish two cases by the parity of t to complete the proof.
Case 1 t is even.
Suppose X be an r-set of
, by Lemma 2.1, we have
. Thus
. Now we discuss the value of
by
.
If
, then
. If
, then
, this contradicts to the choice of X. If
, then we get
Based on the above argument and the definition of the rupture degree, we have
Case 2. t is odd.
Similar to case 1, we directly get
n
Let
in Theorem 2.2, we get the rupture degree of k-uniform hyperpath
.
Corollary 2.3.
.
Let
in Theorem 2.2, we get the rupture degree of k-uniform hyperstar
.
Corollary 2.4.
.
Let
in Theorem 2.2, we get the rupture degree of comet
, which is shown in [7].
Corollary 2.5.
Theorem 2.6. Let
be k-uniform hypergraph that underlies complete t-partite graph
. Then
Proof. Suppose
are the partite sets of
with
for
. Without loss of generality, let
, then
is a vertex cut of
. And then
,
and
. Thus we get
Therefore, we have
On the other hand, based on the fact that for any vertex cut
of
, there exists a partite set
such that
, we have
Thus, by the definition of rupture degree we get
So we get
Let
and
in Theorem 2.6, we get the rupture degree of
and
for
, respectively.
Corollary 2.7.
.
Corollary 2.8.
.
Theorem 2.9 Let
be k-uniform hypergraph underlies cycle
. Then
Proof. Let X be an r-set of
, by Lemma 2.1, we know that
. Note that for any
we have
. So
is an r-set of
. Combine this with the fact
, we get
n
Let
in Theorem 2.9 get the rupture degree of
, which is obtained in [7].
Corollary 2.10.
Theorem 2.11. Let
be a k-uniform hypergraph of complete graph
. Then
Proof. Let X be a cut set of
and suppose
. It is not difficult to get
and
. Thus we have
Let
with
. Note that
, the function
is a monotonically increasing in interval
. So the maximum value of
in interval
is
. Thus by the definition of rupture degree we get
.
Acknowledgements
The author would like to thank anonymous reviewers for their valuable comments and suggests to improve the quality of the article. This work was supported by QHFRP 2020-ZJ-920 and the National Science Foundation of China (No. 11761056).