Research On The Domination Number Of Ⅰ-graphs Ⅰ (n, J, Mj) And Generalized Petersen Graphs P (n, 4)

Domination in graphs is one of the hottest fields of graph theory, and come from a series of application fields. Research on domination in graphs have not only im-portant theoretical, but also varied applications in such fields as design and analysis of communication networks, optimization, social sciences, computational complexity, and algorithm design. As it was proved that determining the domination number of a graph is NP-complete. Because of its difficulty, there are only a few graphs whose domination number have been well researched.In this thesis, we study the domination number of I-graphs and generalized Pe-tersen graphs. First, we prove a sufficient and necessary conditions of I-graphs I(n, j, mj) which have efficient dominating set. Then, we obtain the domination number of I(n, j, mj) with m= 1,2,3. Furthermore, we prove a sharp upper bound for the domination num-ber of P(n,4). There are four chapters in this thesis.In the first chapter, we introduce the research background and progress of domi-nation. Then, we introduce some foundational conceptions of graphs and domination theory. Last, we present the main results of the thesis.In the second chapter, we mainly study the domination number of I-graph I(n, j, mj). First, we prove the properties of I(n, j, j), which deduce the properties of I(n, j, mj). Then, a sufficient and necessary conditions of I-graphs I(n, j, mj) which have efficient dominating set is proved. Meanwhile, we obtain the domination number of I(n, j, mj) withm= 1,2,3.In the third chapter, we mainly study the domination number of generalized Pe-tersen graph P(n,4). Using the method of solving the upper bound for the domination number of P(ck, k), we obtain an upper bound for the domination number of P(n,4).In the fourth chapter, we present the conclusions of our research work and put forward the future work.