Italian Domination On Block Graphs

The Italian dominating function of graph G=?V,E?is the function f satisfying ?_u?N?v?f?u??2 for each vertex v with f?v?=0.w?f?=?_v?Vf?v?is the weight of f.The Italian domination number of G,denoted by?_I?G?,is the minimum weight of f.Let V_i={v:f?v?=i},i=0,1,2.f is an independent Italian dominating function if and only if V₁?V₂is an independent set,and then the minimum weight of f is the independent Italian domination number of G,denoted by i_I?G?.A block is a maximal connected subgraph without cut-vertices.A graph is a block graph if every block of the graph is an complete graph.It is clear that a tree is a special block graph,of which the blocks are all complete graph K₂.Given a connected block graph G,this thesis proposes two linear time algorithms to output?_I?G?and i_I?G?respectively,see Algorithm 3 and Algorithm 4.The Italian domination problem is the deformation of the Roman domination problem.In chapter one,we introduces the origin of Roman domination and Italian domination as well as the domination number algorithm of a tree.In chapter two,we firstly introduces the definition of a block-cutpoint graph and classifies the block-vertices and blocks into three types,then gives the definition of an induced function f_*induced by the function f,and the independent Italian domination number algorithm of a tree is shown there.We proved the?independent?Italian domination number of a block graph G equals to the induced?independent?Italian domination number of its block-cutpoint graph T.Therefore,the?independent?Italian domination problem of a block graph G can be equivalently transformed to the induced?independent?Italian domination problem of the corresponding block-cutpoint graph T.The equivalent transformation theorems of?G,f?and?T,f_*?are given in chapter three and chapter four,see theorem 3.3 and theo-rem 4.4.With the application of dynamic programming,the Italian domination number algorithm and independent Italian domination number algorithm of a connected block graph G are designed through its block-cutpoint graph T on the basis of domination number algorithm and independent Italian domination number algorithm of a tree.