Research On K-power Domination Algorithm In Weighted Graph

The power domination problem in graph theory originates from how to place as few as possible measurement devices units at selected locations in electric power systems.Power domination problem is an important research branch of the domination problem.Let G=（V,E）be a simple graph,a set S（?）V is a dominating set of G if every vertex in V\S is adjacent to at least one vertex in S.The domination number of G,denoted by y（G）,is defined the minimum cardinality of domination set of G.The domination set problem is to determine the domination number.The power domination set S of G,if and only if all vertices of V have a message by following tow ways:（1）every vertex v ∈ S sends a message to itself and all its neighbors;（2）if an observed vertex v has only one unobserved neighbors u,then v will send a message to u.The power domination number of G,is denoted by γp（G）defined the minimum cardinality of power domination set.The power domination set problem is to determine the power domination number.Let k be a nonnegative integer,the definition of k-power domination set S is familiar with the definition power domination set,only the second way is changed to as following:if an observed vertex v has as most k unobserved neighbors,then v will send a message to them.The k-power domination number of G,is denoted by γkp（G）defined the minimum cardinality of k-power domination set.The k-power domination set problem is to determine the k-power domination number.In actual operation,the cost of setting different locations is different.Therefore,the study of weighted k-power domination has great practical value.Let G=（V,E,w）be a weighted graph,S is a k-power domination set,w（S）=Σ_v∈S w（v）is the weighted of S.The weighted k-power domination number is denoted by γkp w（G）,is defined as γ_kp^w（G）=min {w（S）| S is a k-power domination set of G}.In the paper,we study the algorithm of weighted k-power domination number in some special graphs,the main work includes the following parts:In the first chapter,we introduce the research background and current situation of domination set problem,power domination set problem and weighted domination set problem.Haynes et al.have proved the NP-difficulty of power domination problem in general graphs.Some polynomial time algorithms for a variety of domination set problems on special graphs were also discussed.On the weighted special graphs,the algorithms of some domination set problems were also concerned.In the second chapter,based on the conclusion of theorem 2.1,we study the weighted k-power domination set problem in weighted trees.Using the technology of dynamic programming to give a linear time algorithm,and the correctness of the algorithm is proved.In the third chapter,we study the weighted k-power domination set problem in Cactus graphs,the theoretical method of solving the k-power domination problem in weighted circle was given in theorem 3.1.Based on the method of circle and tree,we give an effective algorithm for weighted k-power domination number in Cactus graphs.The algorithm complexity is 0（m + bn）,where m is the number of edges,n is the number of vertices and the number of b for the length of the circle is greater than or equal to 3.And we prove the correctness of the algorithm.