On The Domination Number Of Generalized Petersen Graphs P(n,2) And Circulant Graphs C(n;{1,4})

Graph theory is one of the most important branches of combinatorics. Its wide application accelerates its development. For example, some launchers must be placed in a communication network, requiring each lancher must have a direct communication line with another. How to choose places, making the places with the least lanchers. This problem can be converted to a domination number problem. Caculating the domination of any graph is a NP-complete problem, so there are only a few domination problems of graphs have been solved.In this paper, with the algorithm of calculating the domination number of graphs, the result of the domination number of generalized Petersen graphs P(n,2) and circulant graphs C(n;{1,4}) with n being small are caculated. According to the result, the theorem of the domination number of generalized Petersen graphs P(n,2) and circulant graphs C(n;{1,4}) and the dominating sets of them are given.In order to prove the theorem, the concept of redomination number is brought up. So proving the min domination number is converted to proving the redomination number. According to a series of lemmas, the domination number of generalized Petersen graphs P(n,2) is proved to bethe domination number of circulant graphs C(n; {1,4}) is proved to be...