The Domination Parameters Of Generalized Petersen Graphs And Circulant Graphs

The domination problem is one of the most important branches of graph theory, which has wide application in networks designing. For example, some launchers must be placed in a communication network, requiring each lancher must have a direct communication line with another. The way to choose the places makes 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 the domination numbers of a few classes of graphs have been solved.A set S(?)V(G) is a dominating set if for each v∈V(G), either v∈S or v is adjacent to some w∈S. That is, S is a dominating set if and only if N[S] = V (G). If any subset of S is not a dominating set, then S is a minimal dominating set. If for each minimal dominating set S~*, we have |S~* |≥|S|, we call S is minimum dominating set. The domination numberγ(G) is the cardinality of minimum dominating sets of G.A set S (?) F (G) is an independent set, if there nonexists two vertices of S adjacent with each other. S is a maximal independent set, if for any vertex set the subset of which is S, there exist two vertices adjacent with each other. If for each maximal independent set S~*, we have |S~* |≤|S|, we call S is maximum independent set. The independence number a (G) is the maximum cardinality of an independent set in G.In this paper, with the algorithm of calculating the domination number of graphs, we get the domination number of circulant graphs and the independent number of generalized Petersen graphs with smaller n and k, construct the corresponding dominationg sets and independent sets, find the rules of the sets, and presume the dominationg sets and independent sets with larger with bigger n and k. The supremum of the domination number of circulant graphs C (n; {1, k}), n=3k, Ak and the infimurn of the generalized Petersen graphs P (n, k), k=1, 2, 3, 5 are deserved. According to the result, we prove the infimum of the domination number of circulant graphs C (n; {1, k}), n=3k, 4k and the supremum of the generalized Petersen graphs P (n, k), k=1, 2, 3, 5, and the exact values of them are deserved.