Study On Algorithm Of 2-Rainbow Domination In Block Graphs

Let G be a undirect simple connected graph and let f be a function that assigns to each vertex a set of colors choosen from the set{1,2,…,k}; that is, f:V(G)→>P({1,…, k}). If for each vertex v∈V(G) that f(v)=φwe have Uu∈N[v] f(u)={1,…,k}, then f is called the k-rainbow dominating function (k-RDF) of G. The weight of the function f is defined as w(f)=Σv∈V(G) |f(v)|.The minimum weight of a k-RDF is called the k-rainbow domination number of G, which we denote byγrk(G). The k-rainbow domination problem is to determine the k-rainbow domination number and a minimum k-RDF of any graph G.In this thesis, we begin new research of 2-rainbow domination problem in block graphs which is based on previous results of k-rainbow domination in trees. Firstly, we give a method on traveling an arbitrary block graph block by block. Secondly, we analysis ways on signing some special blocks. We also proved that the 2-rainbow domination problem and 2-weak rainbow domination are equivalent. We define a special structure in block graph—sequence of alternative blocks, and a algorithm (derive algorithm) to find a sequence of alternative blocks in block graph, and give a polynomial time algorithm (M2-WRDF) for 2-weak rain-bow domination problem in block graph.We study the 2-rainbow domination problem of a special Cactus graph—S-Cactus graph. Firstly, we study the 2-rainbow domination problem of cycles. We give the minimum 2-rainbow domination's signing methods of one style cycles (I cycles), and prove that this method is determined when considering the symmetry. Secondly, we consider the S-Cactus graphs withoutⅡcycles, and give a linear time algorithm to get the minimum 2-RDF of S-Cactus graphs withoutⅡcycles finally.