Minimum Dominating Sets in Uncertain Graphs

Power networks, biological networks, and other networks are becoming more and more complex. And corresponding problems of these networks accompany by uncertainty, which can only rely on expert opinion. In practical applications, the dominating ability of these networks is often within the scope of the designer's consideration. It is more appropriate to use uncertain graphs to characterize these networks. And then it is necessary to explore the domination problem in uncertain graphs. As an important parameter, the minimum dominating set of graphs could be used to measure the dominating ability of some complex networks. In the paper, our discussion will focus on the minimum dominating set problem in uncertain graphs. We will first study the domination number of uncertain graphs and show the formulas for calculating the corresponding distribution and its numerical characteristics. Then two models are proposed to find the minimum dominating set in uncertain graphs. Besides, corresponding algorithms for and some examples are also shown.