Independent Double Roman Domination on Block Graphs

Abstract: Given a graph

G = (V, E)

,

f : V i g h t a r r o w 0, 1, 2

is the Italian dominating function of

G

if

f

satisfies

s u m_{u i n N (v)} f (u) g e q 2

when

f (v) = 0

. Denote

w (f) = s u m_{v i n V} f (v)

as the weight of

f

. Let

V_{i} = v : f (v) = i, i = 0, 1, 2

, we call

f

the independent Italian dominating function if

V_{1} c u p V_{2}

is an independent set. The independent Italian domination number of

G

is the minimum weight of independent Italian dominating function

f

, denoted by

i_{I} (G)

. We equivalently transform the independent domination problem of the connected block graph

G

to the induced independent domination problem of its block-cutpoint graph

T

, then a linear time algorithm is given to find

i_{I} (G)

of any connected block graph

G

based on dynamic programming.

This page was built for publication: Independent Double Roman Domination on Block Graphs