| In the past decades,with the rapid development of very large scale integration,the theoretical issues related to the network are getting more and more attention.Especially the reliability of the network has become one of the most concerned issues of experts and scholars.Because the network can be represented by graphs or directed graph.Thus,one can study the property of networks by studying property of graphs,where the connectivity and domination number of the graph are important parametees studying the reliability of the graph.This paper mainly studies connected edge dominating set.This article is divided into five chapters.Chapter 1.It mainly introduces the research background of connectivity and dominating set,as well as related basic concepts and definitions,and briefly describe the research results of the edge dominating set.Chapter 2.With the help of the structural characteristics of the edge dominating set,we construct a connected edge dominating set by the minimum edge dominance set.Through the analysis of the construction process,the structure and size relationship of the edge domination set and the connected edge domination set are obtained.At the same time,this paper gives a feasible algorithm for constructing the connected edge dominating set.Chapter 3.In the process of ear decomposition,by estimating the size relationship between the matching and each ear,we set up the inequality between the matching and 2-(edge)connection edge dominating set.Chapter 4.According to the results of Chapter 2,we get a “dominating tree”whose edge set is a connected edge dominating set of the graph,we construct an induced subgraph of the2-connected edge dominating set.By analysing the above process,we obtain the relationship between the connected edge dominating set and the 2-(edge)connected edge dominating set.At the end of the chapter,we show an algorithm which can contrect a 2-connected edge dominating set of a 2-connected graph.Chapter 5.Summary and follow-up prospects. |
PDF Full Text Request