# A Recursive Formula for the Reliability of ar-Uniform Complete Hypergraph and Its Applications

Authors: Ke Zhang; Haixing Zhao; Zhonglin Ye; Lixin Dong
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The reliability polynomialR
(
S
,
p
) of a finite graph or hypergraph S
=
(
V
,
E
) gives the probability that the operational edges or hyperedges of S induce a connected spanning subgraph or subhypergraph, respectively, assuming that all (hyper)edges of S fail independently with an identical probability q
=
1
-
p. In this paper, we investigate the probability that the hyperedges of a hypergraph with randomly failing hyperedges induce a connected spanning subhypergraph. The computation of the reliability for (hyper)graphs is an NP-hard problem. We provide recurrence relations for the reliability of r-uniform complete hypergraphs with hyperedge failure. Consequently, we determine and calculate the number of connected spanning subhypergraphs with given size in the r-uniform complete hypergraphs.


---

## Body

## 1. Introduction

As we all know, the topological structure of a real-world complex system is often described by a graph. And recently, researchers tend to represent some more complex systems by hypergraphs [1–4]. With the establishment and perfection of the hypergraph theory by Berge et al. [5, 6], many interesting objects in graphs were extended to hypergraphs in a natural way. Since a graph is a 2-uniform hypergraph, many of the corresponding results about graphs could be analogized to hypergraphs, and there exist some representative works. For example, Dankelmann et al. [7] and Zhao et al. [8] obtained several sufficient conditions for hypergraphs to be maximally edge-connected. Gu et al. characterized the degree sequence of a uniform hypergraph, and this degree sequence makes the uniform hypergraph k-edge-connected [9]. In [10] and [11], an upper bound of the sum of squares of degrees in a graph and a hypergraph was given, respectively. Moreover, hypergraph theory can be applied to optimize wireless communication networks [12]. The network reliability analysis and synthesis have attracted much attention and there exist various results in [13–16], but in the same field there exist seldom results for hypergraphs.One of the most common measures in network reliability is the all-terminal reliability [14]. Suppose that G
=
(
V
,
E
) is a graph where the edges independently fail with the same probability q. The all-terminal reliability is the probability that the surviving edges induce a connected spanning subgraph. It can be expressed as a polynomial R
(
G
,
q
)
=
∑
i
=
n
-
1
e
s
i
(
G
)
(
1
-
q
)
i
q
e
-
i, where s
i
(
G
) is the number of connected spanning subgraphs of G containing i edges. The problems of calculating the all-terminal reliability and designing reliable network have been probed and studied deeply in [14].As a generalization of a graph, the hypergraph provides an effective method for network description [1, 2, 17]. A network represented by a hypergraph is called a hypernetwork. More and more researchers are interested in hypergraphs or hypernetworks. The existing literatures about hypernetworks often focus on the establishment of models [18–20] or topological properties [1, 21, 22]. Extensive researches have been conducted in the field of edge-connectivity of hypergraphs [7–9]. In this paper, we investigate the hypernetwork reliability with edge failure.Here we define the probability asR
(
H
,
p
) that the operational edges of the hypergraph H induce a connected spanning subhypergraph. Our main results are recurrence relations for the calculation of R
(
K
n
r
,
p
), where K
n
r denotes the r-uniform complete hypergraphs of order n. Consequently, we provide a new method to calculate the number of connected spanning subhypergraphs in K
n
r. The r-uniform complete hypergraphs have long been in the focus of hypernetwork reliability research for different reasons. They appear as subhypergraphs in larger hypernetworks usually. They are the densest ones among all r-uniform hypergraphs, so if we obtain the reliability of the r-uniform complete hypergraphs, the upper bounds of the reliability of the r-uniform hypergraphs can be found satisfactory. And they have a nice combinatorial structure that allows researcher to explore their symmetry. For some applications, see [23–25].In [26] Gilbert presented a recursive algorithm for the calculation of the all-terminal reliability of a complete graph K
n by fixing a vertex v
∈
V and considered the relationships between all connected subgraphs containing v of order k and corresponding subgraphs of order n
-
k, then the probability R
(
K
n
,
p
) is exactly equivalent to the probability that the induced spanning subgraph is connected for n vertices set. We substantially generalize this idea and propose the result in hypergraphs based on above analogies, and the research result from Gilbert is a special case of the research achievements proposed by this paper.Trees are among the most fundamental, useful, and understandable objects in all of graph theory. This kind of common sense is also true for hypergraphs [27–29]. Another important part of this paper is to generalize the notion of a tree to uniform hypergraphs and to investigate enumeration of connected spanning subhypergraphs, as to calculate the number of spanning hypertrees in r-uniform complete hypergraphs.The network reliability with the edge failure is closely related to the number of spanning trees of the corresponding graph [30]. We obtain the number of spanning hypertrees in r-uniform complete hypergraphs with the inspiration of such a similar relationship in general graphs.The remaining parts of this paper are organized as follows. Firstly, we introduce some necessary definitions and notations. Then we present recursive relations for the reliability polynomial with edge failure of ar-uniform complete hypergraph. Counting spanning hypertree in a r-uniform complete hypergraph is researched in Section 3. Consequently, we finish the entire paper with some conclusions and open problems in Section 4.


### 1.1. Nomenclature and Definitions

Many definitions of hypergraphs would be naturally extended from graphs; undefined terms can be found in [5, 6]. A hypergraph H is a pair (
V
,
ε
), where V is the vertex set of H and ε is a collection of distinct nonempty subsets of V. An element in ε is a hyperedge or simply an edge of H. We consider the hypergraph with no isolated vertices, which are not contained in any edge. Let ε
=
E
1
,
E
2
,
⋯
,
E
m. A hypergraph H is simple hypergraph if E
i
⊆
E
j implies that i
=
j for any i
,
j with 1
≤
i
,
j
≤
m. The hypergraphs researched in this paper are simple hypergraphs. A hypergraph H is a r-uniform hypergraph if E
i
=
r for each i with 1
≤
i
≤
m. Thus, a graph is a 2-uniform hypergraph, and vice versa. Let n
,
r be integer and hold 2
≤
r
≤
n
-
1.We define the r-uniform complete hypergraph of order n as a hypergraph denoted as K
n
r containing all the r-subsets of the set V of cardinality n.In the following parts, we conduct the same researches about reliability with edge failure of graphs on hypergraphs. Letv denote an arbitrary vertex in H. We assume that all edges of H fail independently with identical probability q. The surviving subhypergraph of H is called the connected spanning subhypergraph of H. The reliability polynomial R
(
H
,
q
) gives the probability of the surviving subhypergraph of a hypergraph H
(
V
,
ε
).The reliability polynomial of a hypergraph is often presented in the literature asR
(
H
,
p
) with p
=
1
-
q. We write R
(
H
,
q
) for simpler presentation as a function of the edge failure probability q.The tree is an important object in graph theory, and the number of spanning trees of a graph is closely related to the reliability of this graph [30]. The definition of a tree could be extended to the hypergraph, which is consequently called a hypertree or simply a tree. Although there are many statements of the definition of a tree in graph theory, these statements are equivalent and intuitive. However, the generalization of the definition of a tree in hypergraphs is much more complicated, and descriptions of these definitions are completely different [27–29]. In this paper, a hypertree is defined as a connected hypergraph which is disconnected by removing any edge among the edge set [27]. A spanning hypertree of H is a spanning subhypergraph with the minimum number of edges of H that is a hypertree. We denote the number of spanning trees of H by τ
(
H
).With regard to the lower bound of the number of edges of connectedr-uniform hypergraphs, Lai et al. [9] give the following results.Theorem 1.
LetH be a r-uniform hypergraph with n vertexes. If H is connected, then m
≥
n
-
1
/
r
-
1. Moreover, the equality holds if and only if H
-
E has r components for any edge E which belongs to ε
(
H
).


## 1.1. Nomenclature and Definitions

Many definitions of hypergraphs would be naturally extended from graphs; undefined terms can be found in [5, 6]. A hypergraph H is a pair (
V
,
ε
), where V is the vertex set of H and ε is a collection of distinct nonempty subsets of V. An element in ε is a hyperedge or simply an edge of H. We consider the hypergraph with no isolated vertices, which are not contained in any edge. Let ε
=
E
1
,
E
2
,
⋯
,
E
m. A hypergraph H is simple hypergraph if E
i
⊆
E
j implies that i
=
j for any i
,
j with 1
≤
i
,
j
≤
m. The hypergraphs researched in this paper are simple hypergraphs. A hypergraph H is a r-uniform hypergraph if E
i
=
r for each i with 1
≤
i
≤
m. Thus, a graph is a 2-uniform hypergraph, and vice versa. Let n
,
r be integer and hold 2
≤
r
≤
n
-
1.We define the r-uniform complete hypergraph of order n as a hypergraph denoted as K
n
r containing all the r-subsets of the set V of cardinality n.In the following parts, we conduct the same researches about reliability with edge failure of graphs on hypergraphs. Letv denote an arbitrary vertex in H. We assume that all edges of H fail independently with identical probability q. The surviving subhypergraph of H is called the connected spanning subhypergraph of H. The reliability polynomial R
(
H
,
q
) gives the probability of the surviving subhypergraph of a hypergraph H
(
V
,
ε
).The reliability polynomial of a hypergraph is often presented in the literature asR
(
H
,
p
) with p
=
1
-
q. We write R
(
H
,
q
) for simpler presentation as a function of the edge failure probability q.The tree is an important object in graph theory, and the number of spanning trees of a graph is closely related to the reliability of this graph [30]. The definition of a tree could be extended to the hypergraph, which is consequently called a hypertree or simply a tree. Although there are many statements of the definition of a tree in graph theory, these statements are equivalent and intuitive. However, the generalization of the definition of a tree in hypergraphs is much more complicated, and descriptions of these definitions are completely different [27–29]. In this paper, a hypertree is defined as a connected hypergraph which is disconnected by removing any edge among the edge set [27]. A spanning hypertree of H is a spanning subhypergraph with the minimum number of edges of H that is a hypertree. We denote the number of spanning trees of H by τ
(
H
).With regard to the lower bound of the number of edges of connectedr-uniform hypergraphs, Lai et al. [9] give the following results.Theorem 1.
LetH be a r-uniform hypergraph with n vertexes. If H is connected, then m
≥
n
-
1
/
r
-
1. Moreover, the equality holds if and only if H
-
E has r components for any edge E which belongs to ε
(
H
).


## 2. A Recursive Formula for the Reliability of ar-Uniform Complete Hypergraph

In this section, we present a recurrence relation for the computation of the reliability polynomial ofr-uniform complete hypergraphs. As a preparation, we restate a classical theorem concerning the all-terminal reliability of a complete graph. By distinguishing one vertex of a complete graph, Gilbert [26] obtained the following results.Theorem 2.
The reliability polynomial of the complete graphK
n
(
n
≥
2
) satisfies the following recurrence relations:(1)
R
K
n
,
q
=
1
-
∑
k
=
1
n
-
1
n
-
1
k
-
1
R
K
k
,
q
q
k
n
-
k
.Equation (1) and the initial condition R
(
K
1
,
q
)
=
1 uniquely determine the value R
(
K
n
,
q
).


### 2.1. The Reliability of ar-Uniform Complete Hypergraph

Now we consider the reliability of ar-uniform complete hypergraph. In view of Theorem 2 we investigate the reliability polynomial of the r-uniform complete hypergraph. Our main result below generalizes Gilbert’s result.Theorem 3.
The reliability polynomial of ther-uniform complete hypergraph K
n
r, where n
≥
2, 2
≤
r
≤
n
-
1, satisfies the following recurrence relations: (2)
R
K
n
r
,
q
=
1
-
n
-
1
0
R
K
1
,
q
q
n
-
1
r
-
1
-
∑
k
=
r
n
-
1
n
-
1
k
-
1
R
K
k
r
,
q
q
n
r
-
k
r
-
n
-
k
r
. Equation (2) uniquely determines R
(
K
n
r
,
q
) based on the initial values R
(
K
1
,
q
)
=
1, R
(
K
k
k
,
q
)
=
1
-
q, and the condition n
m
=
0
(
n
<
m
).Proof.
Let us fix a vertexv
∈
V
(
K
n
r
). The proof process is completed by the following two steps.
Step 1. The first quantity on the right side of the equation that is subtracted from 1 is equal to q
n
-
1
r
-
1, which gives the probability that makes the vertex v isolated from the K
n
r. There are n
-
1
r
-
1 edges in K
n
r containing v.
Step 2. The second quantity is the form of summation as ∑
k
=
r
n
-
1
n
-
1
k
-
1
R
(
K
k
r
,
q
)
q
n
r
-
k
r
-
n
-
k
r, which gives the probability that the root vertex v exactly builds the connected component with k
-
1 vertices, where all such connected components of order k must contain vertex v. There are n
-
1
k
-
1 possible items to select the vertex set A of order k
-
1 in the remaining n
-
1 vertices. Then R
(
K
k
r
,
q
) is the probability that the set B
=
A
∪
v induces a connected subhypergraph. In the special case r
=
k, the hypergraph with only one edge containing all k vertices is denoted as K
k
k. According to the definition of the reliability of the hypernetwork with the edge failure, we can obtain R
(
K
k
k
,
q
)
=
1
-
q. The expression q
n
r
-
k
r
-
n
-
k
r is the probability that all edges fail between K
n
r
-
B and B in r-uniform complete hypergraph K
n
r. Finally, we adopt the expression n
r
-
k
r
-
n
-
k
r to calculate the number of edges connecting a component of order n
-
k and the other induced by B.In Theorem3, the special case r
=
2 is the Gilbert’s result in Theorem 2.Table1 shows some polynomials for the reliability of r-uniform complete hypergraphs K
n
r of orders 4, 5, 6, and 7.Table 1
Reliability polynomial for small hypergraphs.
r
n
4
5
6
7
3
1
-
4
q
3
+
3
q
4
1
-
5
q
6
+
10
q
9
-
6
q
10
1
-
6
q
10
+
15
q
16
-
10
q
18
1
-
7
q
15
+
21
q
25
-
35
q
30
+
140
q
33
-
210
q
34
+90q
35
4
1
-
5
q
4
+
4
q
5
1
-
6
q
10
+
15
q
14
-
10
q
15
1
-
7
q
20
+
21
q
30
-
35
q
34
+
20
q
35
5
1
-
6
q
5
+
5
q
6
1
-
7
q
15
+
21
q
20
-
15
q
21
6
1
-
7
q
6
+
6
q
7Whenr approximates n, the terms in the recurrence for calculating R
(
K
n
r
,
q
) are finite in Theorem 3, so we can get the expression of R
(
K
n
r
,
q
) about n. The following Corollary 4 can be yielded by setting r
=
n
-
1
,
n
-
2, and n
-
3.Corollary 4.
The reliability polynomials of the complete hypergraphK
n
r with r
=
n
-
1
,
n
-
2, and n
-
3 are given by the following: (3)
R
K
n
n
-
1
,
q
=
1
-
n
q
n
-
1
+
n
-
1
q
n
n
≥
3
;
R
K
n
n
-
2
,
q
=
1
-
n
q
n
-
1
2
+
n
2
q
n
2
-
1
-
n
-
1
2
q
n
2
n
≥
4
;
R
K
n
n
-
3
,
q
=
1
-
n
q
n
-
1
3
+
n
2
q
n
3
-
n
+
2
-
n
3
q
n
3
-
1
+
n
-
1
3
q
n
3
n
≥
5
.


## 2.1. The Reliability of ar-Uniform Complete Hypergraph

Now we consider the reliability of ar-uniform complete hypergraph. In view of Theorem 2 we investigate the reliability polynomial of the r-uniform complete hypergraph. Our main result below generalizes Gilbert’s result.Theorem 3.
The reliability polynomial of ther-uniform complete hypergraph K
n
r, where n
≥
2, 2
≤
r
≤
n
-
1, satisfies the following recurrence relations: (2)
R
K
n
r
,
q
=
1
-
n
-
1
0
R
K
1
,
q
q
n
-
1
r
-
1
-
∑
k
=
r
n
-
1
n
-
1
k
-
1
R
K
k
r
,
q
q
n
r
-
k
r
-
n
-
k
r
. Equation (2) uniquely determines R
(
K
n
r
,
q
) based on the initial values R
(
K
1
,
q
)
=
1, R
(
K
k
k
,
q
)
=
1
-
q, and the condition n
m
=
0
(
n
<
m
).Proof.
Let us fix a vertexv
∈
V
(
K
n
r
). The proof process is completed by the following two steps.
Step 1. The first quantity on the right side of the equation that is subtracted from 1 is equal to q
n
-
1
r
-
1, which gives the probability that makes the vertex v isolated from the K
n
r. There are n
-
1
r
-
1 edges in K
n
r containing v.
Step 2. The second quantity is the form of summation as ∑
k
=
r
n
-
1
n
-
1
k
-
1
R
(
K
k
r
,
q
)
q
n
r
-
k
r
-
n
-
k
r, which gives the probability that the root vertex v exactly builds the connected component with k
-
1 vertices, where all such connected components of order k must contain vertex v. There are n
-
1
k
-
1 possible items to select the vertex set A of order k
-
1 in the remaining n
-
1 vertices. Then R
(
K
k
r
,
q
) is the probability that the set B
=
A
∪
v induces a connected subhypergraph. In the special case r
=
k, the hypergraph with only one edge containing all k vertices is denoted as K
k
k. According to the definition of the reliability of the hypernetwork with the edge failure, we can obtain R
(
K
k
k
,
q
)
=
1
-
q. The expression q
n
r
-
k
r
-
n
-
k
r is the probability that all edges fail between K
n
r
-
B and B in r-uniform complete hypergraph K
n
r. Finally, we adopt the expression n
r
-
k
r
-
n
-
k
r to calculate the number of edges connecting a component of order n
-
k and the other induced by B.In Theorem3, the special case r
=
2 is the Gilbert’s result in Theorem 2.Table1 shows some polynomials for the reliability of r-uniform complete hypergraphs K
n
r of orders 4, 5, 6, and 7.Table 1
Reliability polynomial for small hypergraphs.
r
n
4
5
6
7
3
1
-
4
q
3
+
3
q
4
1
-
5
q
6
+
10
q
9
-
6
q
10
1
-
6
q
10
+
15
q
16
-
10
q
18
1
-
7
q
15
+
21
q
25
-
35
q
30
+
140
q
33
-
210
q
34
+90q
35
4
1
-
5
q
4
+
4
q
5
1
-
6
q
10
+
15
q
14
-
10
q
15
1
-
7
q
20
+
21
q
30
-
35
q
34
+
20
q
35
5
1
-
6
q
5
+
5
q
6
1
-
7
q
15
+
21
q
20
-
15
q
21
6
1
-
7
q
6
+
6
q
7Whenr approximates n, the terms in the recurrence for calculating R
(
K
n
r
,
q
) are finite in Theorem 3, so we can get the expression of R
(
K
n
r
,
q
) about n. The following Corollary 4 can be yielded by setting r
=
n
-
1
,
n
-
2, and n
-
3.Corollary 4.
The reliability polynomials of the complete hypergraphK
n
r with r
=
n
-
1
,
n
-
2, and n
-
3 are given by the following: (3)
R
K
n
n
-
1
,
q
=
1
-
n
q
n
-
1
+
n
-
1
q
n
n
≥
3
;
R
K
n
n
-
2
,
q
=
1
-
n
q
n
-
1
2
+
n
2
q
n
2
-
1
-
n
-
1
2
q
n
2
n
≥
4
;
R
K
n
n
-
3
,
q
=
1
-
n
q
n
-
1
3
+
n
2
q
n
3
-
n
+
2
-
n
3
q
n
3
-
1
+
n
-
1
3
q
n
3
n
≥
5
.


## 3. Enumeration of Spanning Hypertrees inr-Uniform Complete Hypergraphs

### 3.1. Standard Version from the Recurrence

In the following, we give the equivalent operation of the recurrence formula, then we can get some properties of the correspondingr-uniform complete hypergraph. For example, we investigate the number of connected spanning subhypergraphs induced by the operational edges of a r-uniform complete hypergraph with random failure of edges. In particular, the number of spanning trees of a complete hypergraph can be obtained directly. In a similar way proposed by the reliability of graph, the all-terminal reliability of a hypergraph can be defined as an equivalent form, which is the homogeneous polynomial of 1
-
q and q. For a r-uniform complete hypergraph, this standard form is as follows: (4)
R
K
n
r
,
q
=
∑
i
=
0
n
r
s
i
K
n
r
1
-
q
i
q
n
r
-
i
,where s
i
(
K
n
r
) denotes the number of connected spanning subhypergraphs containing i edges in a r-uniform complete hypergraph.We now give an example of transformation of the reliability polynomialR
(
K
6
3
,
q
) as follows.Example 5.
(5)
R
K
6
3
,
q
=
1
-
6
q
10
+
15
q
16
-
10
q
18
=
∑
i
=
0
20
20
i
1
-
q
i
q
20
-
i
-
6
∑
i
=
0
10
10
i
1
-
q
i
q
10
-
i
q
10
+
15
∑
i
=
0
4
4
i
1
-
q
i
q
4
-
i
q
16
-
10
∑
i
=
0
2
2
i
1
-
q
i
q
2
-
i
q
18
=
480
1
-
q
3
q
17
+
3600
1
-
q
4
q
16
+
13992
1
-
q
5
q
15
+
31200
1
-
q
6
q
14
+
76800
1
-
q
7
q
13
+
125700
1
-
q
8
q
12
+
167900
1
-
q
9
q
11
+
184750
1
-
q
10
q
10
+
∑
i
=
11
20
20
i
1
-
q
i
q
20
-
i
.
From these equations, we find thatK
6
3 does not contain the connected subhypergraph with 2 edges. The number of spanning hypertrees is 480, the number of connected spanning subhypergraphs with 4 edges is 3600, and so on.


### 3.2. The Number of Spanning Hypertrees inr-Uniform Complete Hypergraphs

According to the definition of the hypertree in this paper and the theory of network reliability, the spanning hypertree ofr-uniform complete hypergraph means a connected spanning subhypergraph with the minimum number of edges. The hypergraph H
1
=
(
V
,
ε
1
) is one example, where V
=
{
1
,
2
,
3
,
4
,
5
}, ε
1
=
{
E
1
=
{
1,2
,
5
}
,
E
2
=
{
3,4
,
5
}
}. And the hypergraph H
2
=
(
V
,
ε
2
) is another example, where V
=
{
1
,
2
,
3
,
4
,
5
}, ε
2
=
{
E
1
=
{
1,4
,
5
}
,
E
2
=
{
2,4
,
5
}
,
{
3,4
,
5
}
}
. Both H
1 and H
2 are spanning subhypergraphs of K
5
3, and they are all hypertrees. By Theorem 1, a 3-uniform hypergraphs with 5 vertices have at least 2 edges. ε
1
=
2, so H
1 is a spanning hypertree of K
5
3; ε
2
=
3, so H
2 is not a spanning hypertree of K
5
3; it is a hypertree and a spanning subhypergraph of K
5
3. Clearly, τ
(
K
5
3
)
=
15 and the number of spanning subhypergraphs with hypertree structure in K
5
3 is 25. We find that the spanning hypertree of r-uniform complete hypergraph is a hypertree and a spanning subhypergraph, but the reverse is not true.Combined with the above recurrence relation of ther-uniform complete hypergraph K
n
r
(
n
≥
2,2
≤
r
≤
n
-
1
) and its equivalent standard conversion, we can get the number of spanning trees in K
n
r.Lemma 6.
The number of spanning hypertrees inK
n
r is given by the following:(6)
τ
K
n
r
=
s
n
-
1
/
r
-
1
K
n
r
.Proof.
LetH be a connected spanning subhypergraph of K
n
r. To make H become a spanning hypertree of K
n
r, if the edge number of H denotes m
(
S
T
), for the Theorem 1, m
(
S
T
)
≥
n
-
1
/
r
-
1 must be first condition.
Case 1. If n
-
1
/
r
-
1 is an integer, then m
(
S
T
)
=
n
-
1
/
r
-
1.
Case 2. If n
-
1
=
k
(
r
-
1
)
+
t, where k is a nonnegative integer and t
=
1,2
,
⋯
,
r
-
2
,then m
(
S
T
)
=
k
+
1
.
Based on Cases 1 and 2, the conclusions we need to prove have been established.Table2 shows the number of spanning trees of r-uniform complete hypergraphs K
n
r of orders 4, 5, 6, 7, and 8.Table 2
The number of spanning trees for small hypergraphs.
r
n
4
5
6
7
8
3
6
15
480
735
117810
4
10
45
70
14560
5
15
105
280
6
21
210
7
28According to the definition of the spanning hypertree above and standard expression of reliability inr-uniform complete hypergraphs, the result of Lemma 6 is intuitive and true for all hypergraphs. However, it is difficult to solve all the counting problems of the spanning hypertrees in general hypergraphs, it needs to be furtherly explored in the future research.About enumeration of spanning hypertrees inK
n
r, for some special cases, we get some results as follows.Theorem 7.
If1
≤
k
≤
n
/
2 and K
n
r (r
=
n
-
k) is a r-uniform complete hypergraph with order n, then(7)
a
τ
K
n
r
=
n
k
2
-
n
-
1
k
-
1
2
-
∑
r
=
1
k
-
1
n
-
1
r
τ
K
n
-
r
n
-
k
;
b
τ
K
n
r
=
1
2
n
2
k
2
k
k
.Proof.
LetK
n
r
(
r
=
n
-
k
,
1
≤
k
≤
n
/
2
) be a r-uniform complete hypergraph with order n. By Lemma 6, we have τ
(
K
n
n
-
k
)
=
s
2
K
n
n
-
k
(
1
≤
k
≤
n
/
2
)
.And by the standard expression of the recursive formula of R
(
K
n
n
-
k
) in Theorem 3, we can deduce s
2
K
n
n
-
k
=
n
k
2
-
n
-
1
k
-
1
2
-
∑
r
=
1
k
-
1
n
-
1
r
τ
(
K
n
-
r
n
-
k
), so the first equality in the equation holds.
On the other hand, the edge number of spanning hypertrees inK
n
n
-
k s is exactly equal to 2, from the perspective of combinatorics; the number of the spanning hypertrees τ
K
n
r in K
n
n
-
k s is 1
/
2
n
2
k
2
k
k.
So far, we have completed the proof of Theorem7.Remark 8.
By Theorem7 and let τ
(
K
n
-
r
n
-
k
)
=
1
/
2
n
-
r
2
k
-
2
r
2
k
-
2
r
k
-
r, we have the equation as follows:(8)
n
k
2
-
n
-
1
k
-
1
2
-
1
2
∑
r
=
1
k
-
1
n
-
1
r
n
-
r
2
k
-
2
r
2
k
-
2
r
k
-
r
=
1
2
n
2
k
2
k
k
.
As a corollary to Theorem7, we obtain the result that the number of spanning hypertrees in special cases of r-uniform complete hypergraphs.Corollary 9.
LetK
n
r be a r-uniform complete hypergraphs of order n
,when r
=
n
-
1
,
n
-
2
,
n
-
3
(9)
τ
K
n
n
-
1
=
n
2
n
≥
3
;
τ
K
n
n
-
2
=
3
n
4
n
≥
5
;
τ
K
n
n
-
3
=
10
n
6
n
≥
7
.Proof.
The transformation of the recurrence in Theorem3 is the homogeneous polynomial ∑
i
=
0
n
r
s
i
(
K
n
r
)
(
1
-
q
)
i
q
n
r
-
i. According to the definition of the spanning hypertree of a r-uniform complete hypergraph, we achieve some interesting conclusions as follows:(10)
τ
K
n
n
-
1
=
s
2
K
n
n
-
1
=
n
2
n
≥
3
;
τ
K
n
n
-
2
=
s
2
K
n
n
-
2
=
n
2
2
-
n
-
1
2
-
n
-
1
n
-
1
2
=
3
n
4
n
≥
5
;
τ
K
n
n
-
3
=
s
2
K
n
n
-
3
=
n
3
2
-
n
-
1
2
2
-
n
-
1
2
n
-
2
2
-
n
-
1
τ
K
n
-
1
n
-
3
=
10
n
6
n
≥
7
.In a similar fashion as stated in Theorem7, we can prove the following statement for τ
K
2
n
n.Theorem 10.
LetK
2
n
n be a n-uniform complete hypergraph with order 2
n, then(11)
τ
K
2
n
n
=
2
n
n
3
-
2
n
-
1
n
3
-
∑
r
=
1
n
-
1
2
n
-
1
n
-
1
+
r
S
3
K
n
+
r
n
.Remark 11.
Becauses
2
(
K
2
n
n
)
=
0, so we can get(12)
2
n
n
2
-
2
n
-
1
n
2
=
2
n
-
1
n
+
1
2
∑
r
=
1
n
-
1
2
n
-
1
n
+
r
-
1
n
+
r
2
r
2
r
r
.


## 3.1. Standard Version from the Recurrence

In the following, we give the equivalent operation of the recurrence formula, then we can get some properties of the correspondingr-uniform complete hypergraph. For example, we investigate the number of connected spanning subhypergraphs induced by the operational edges of a r-uniform complete hypergraph with random failure of edges. In particular, the number of spanning trees of a complete hypergraph can be obtained directly. In a similar way proposed by the reliability of graph, the all-terminal reliability of a hypergraph can be defined as an equivalent form, which is the homogeneous polynomial of 1
-
q and q. For a r-uniform complete hypergraph, this standard form is as follows: (4)
R
K
n
r
,
q
=
∑
i
=
0
n
r
s
i
K
n
r
1
-
q
i
q
n
r
-
i
,where s
i
(
K
n
r
) denotes the number of connected spanning subhypergraphs containing i edges in a r-uniform complete hypergraph.We now give an example of transformation of the reliability polynomialR
(
K
6
3
,
q
) as follows.Example 5.
(5)
R
K
6
3
,
q
=
1
-
6
q
10
+
15
q
16
-
10
q
18
=
∑
i
=
0
20
20
i
1
-
q
i
q
20
-
i
-
6
∑
i
=
0
10
10
i
1
-
q
i
q
10
-
i
q
10
+
15
∑
i
=
0
4
4
i
1
-
q
i
q
4
-
i
q
16
-
10
∑
i
=
0
2
2
i
1
-
q
i
q
2
-
i
q
18
=
480
1
-
q
3
q
17
+
3600
1
-
q
4
q
16
+
13992
1
-
q
5
q
15
+
31200
1
-
q
6
q
14
+
76800
1
-
q
7
q
13
+
125700
1
-
q
8
q
12
+
167900
1
-
q
9
q
11
+
184750
1
-
q
10
q
10
+
∑
i
=
11
20
20
i
1
-
q
i
q
20
-
i
.
From these equations, we find thatK
6
3 does not contain the connected subhypergraph with 2 edges. The number of spanning hypertrees is 480, the number of connected spanning subhypergraphs with 4 edges is 3600, and so on.


## 3.2. The Number of Spanning Hypertrees inr-Uniform Complete Hypergraphs

According to the definition of the hypertree in this paper and the theory of network reliability, the spanning hypertree ofr-uniform complete hypergraph means a connected spanning subhypergraph with the minimum number of edges. The hypergraph H
1
=
(
V
,
ε
1
) is one example, where V
=
{
1
,
2
,
3
,
4
,
5
}, ε
1
=
{
E
1
=
{
1,2
,
5
}
,
E
2
=
{
3,4
,
5
}
}. And the hypergraph H
2
=
(
V
,
ε
2
) is another example, where V
=
{
1
,
2
,
3
,
4
,
5
}, ε
2
=
{
E
1
=
{
1,4
,
5
}
,
E
2
=
{
2,4
,
5
}
,
{
3,4
,
5
}
}
. Both H
1 and H
2 are spanning subhypergraphs of K
5
3, and they are all hypertrees. By Theorem 1, a 3-uniform hypergraphs with 5 vertices have at least 2 edges. ε
1
=
2, so H
1 is a spanning hypertree of K
5
3; ε
2
=
3, so H
2 is not a spanning hypertree of K
5
3; it is a hypertree and a spanning subhypergraph of K
5
3. Clearly, τ
(
K
5
3
)
=
15 and the number of spanning subhypergraphs with hypertree structure in K
5
3 is 25. We find that the spanning hypertree of r-uniform complete hypergraph is a hypertree and a spanning subhypergraph, but the reverse is not true.Combined with the above recurrence relation of ther-uniform complete hypergraph K
n
r
(
n
≥
2,2
≤
r
≤
n
-
1
) and its equivalent standard conversion, we can get the number of spanning trees in K
n
r.Lemma 6.
The number of spanning hypertrees inK
n
r is given by the following:(6)
τ
K
n
r
=
s
n
-
1
/
r
-
1
K
n
r
.Proof.
LetH be a connected spanning subhypergraph of K
n
r. To make H become a spanning hypertree of K
n
r, if the edge number of H denotes m
(
S
T
), for the Theorem 1, m
(
S
T
)
≥
n
-
1
/
r
-
1 must be first condition.
Case 1. If n
-
1
/
r
-
1 is an integer, then m
(
S
T
)
=
n
-
1
/
r
-
1.
Case 2. If n
-
1
=
k
(
r
-
1
)
+
t, where k is a nonnegative integer and t
=
1,2
,
⋯
,
r
-
2
,then m
(
S
T
)
=
k
+
1
.
Based on Cases 1 and 2, the conclusions we need to prove have been established.Table2 shows the number of spanning trees of r-uniform complete hypergraphs K
n
r of orders 4, 5, 6, 7, and 8.Table 2
The number of spanning trees for small hypergraphs.
r
n
4
5
6
7
8
3
6
15
480
735
117810
4
10
45
70
14560
5
15
105
280
6
21
210
7
28According to the definition of the spanning hypertree above and standard expression of reliability inr-uniform complete hypergraphs, the result of Lemma 6 is intuitive and true for all hypergraphs. However, it is difficult to solve all the counting problems of the spanning hypertrees in general hypergraphs, it needs to be furtherly explored in the future research.About enumeration of spanning hypertrees inK
n
r, for some special cases, we get some results as follows.Theorem 7.
If1
≤
k
≤
n
/
2 and K
n
r (r
=
n
-
k) is a r-uniform complete hypergraph with order n, then(7)
a
τ
K
n
r
=
n
k
2
-
n
-
1
k
-
1
2
-
∑
r
=
1
k
-
1
n
-
1
r
τ
K
n
-
r
n
-
k
;
b
τ
K
n
r
=
1
2
n
2
k
2
k
k
.Proof.
LetK
n
r
(
r
=
n
-
k
,
1
≤
k
≤
n
/
2
) be a r-uniform complete hypergraph with order n. By Lemma 6, we have τ
(
K
n
n
-
k
)
=
s
2
K
n
n
-
k
(
1
≤
k
≤
n
/
2
)
.And by the standard expression of the recursive formula of R
(
K
n
n
-
k
) in Theorem 3, we can deduce s
2
K
n
n
-
k
=
n
k
2
-
n
-
1
k
-
1
2
-
∑
r
=
1
k
-
1
n
-
1
r
τ
(
K
n
-
r
n
-
k
), so the first equality in the equation holds.
On the other hand, the edge number of spanning hypertrees inK
n
n
-
k s is exactly equal to 2, from the perspective of combinatorics; the number of the spanning hypertrees τ
K
n
r in K
n
n
-
k s is 1
/
2
n
2
k
2
k
k.
So far, we have completed the proof of Theorem7.Remark 8.
By Theorem7 and let τ
(
K
n
-
r
n
-
k
)
=
1
/
2
n
-
r
2
k
-
2
r
2
k
-
2
r
k
-
r, we have the equation as follows:(8)
n
k
2
-
n
-
1
k
-
1
2
-
1
2
∑
r
=
1
k
-
1
n
-
1
r
n
-
r
2
k
-
2
r
2
k
-
2
r
k
-
r
=
1
2
n
2
k
2
k
k
.
As a corollary to Theorem7, we obtain the result that the number of spanning hypertrees in special cases of r-uniform complete hypergraphs.Corollary 9.
LetK
n
r be a r-uniform complete hypergraphs of order n
,when r
=
n
-
1
,
n
-
2
,
n
-
3
(9)
τ
K
n
n
-
1
=
n
2
n
≥
3
;
τ
K
n
n
-
2
=
3
n
4
n
≥
5
;
τ
K
n
n
-
3
=
10
n
6
n
≥
7
.Proof.
The transformation of the recurrence in Theorem3 is the homogeneous polynomial ∑
i
=
0
n
r
s
i
(
K
n
r
)
(
1
-
q
)
i
q
n
r
-
i. According to the definition of the spanning hypertree of a r-uniform complete hypergraph, we achieve some interesting conclusions as follows:(10)
τ
K
n
n
-
1
=
s
2
K
n
n
-
1
=
n
2
n
≥
3
;
τ
K
n
n
-
2
=
s
2
K
n
n
-
2
=
n
2
2
-
n
-
1
2
-
n
-
1
n
-
1
2
=
3
n
4
n
≥
5
;
τ
K
n
n
-
3
=
s
2
K
n
n
-
3
=
n
3
2
-
n
-
1
2
2
-
n
-
1
2
n
-
2
2
-
n
-
1
τ
K
n
-
1
n
-
3
=
10
n
6
n
≥
7
.In a similar fashion as stated in Theorem7, we can prove the following statement for τ
K
2
n
n.Theorem 10.
LetK
2
n
n be a n-uniform complete hypergraph with order 2
n, then(11)
τ
K
2
n
n
=
2
n
n
3
-
2
n
-
1
n
3
-
∑
r
=
1
n
-
1
2
n
-
1
n
-
1
+
r
S
3
K
n
+
r
n
.Remark 11.
Becauses
2
(
K
2
n
n
)
=
0, so we can get(12)
2
n
n
2
-
2
n
-
1
n
2
=
2
n
-
1
n
+
1
2
∑
r
=
1
n
-
1
2
n
-
1
n
+
r
-
1
n
+
r
2
r
2
r
r
.


## 4. Conclusions and Open Problems

In this paper, a recursive algorithm is proposed for calculating the all-terminal reliability of ar-uniform complete hypergraph. Because the 2-uniform hypergraph is a graph, and the computation of the all-terminal reliability of network is an NP-hard problem [31], we know that the computation of reliability of hypernetwork is also NP-hard problem indirectly. The symmetry of the K
n leads to the fact that all-terminal reliability R
(
K
n
,
q
) can be calculated in quadratic time using Theorem 2. We also use the symmetry of the K
n
r, so R
(
K
n
r
,
q
) can be calculated in time Ο
(
n
2
) using Theorem 3. The algorithm presented here is a major improvement over complete state enumeration of common approaches.There still exist some interesting open questions for future research in this field:(i)
How can we get a recurrence relation for theK-Terminal reliability polynomial of a r-uniform complete hypergraph?
(ii)
How can we calculate 2-edge-connected (or higher) reliability ofr-uniform complete hypergraph?
(iii)
How can we calculate more about the result of the number of spanning hypertrees inr
-uniform complete hypergraph?For ar-uniform complete hypergraph K
n
r, when r is a constant, it is very challenging to get the expression of τ
(
K
n
r
) which is just about n and r [28]. According to the recursive relations of reliability of K
n
r proposed in this paper and combinatorics, new progress is expected to be made in solving such problems.(iv)
How can we attack the problem for general hypergraphs?



---

*Source: 3131087-2018-10-14.xml*