Roman domination and double Roman domination numbers of Sierpiński graphs \(S(K_n,t)\) (Q2239024)

Sierpiński graph \(S_n^t\) can be defined recursively as \(S_n^1\cong K_n\) and one obtains \(S_n^{t+1}\) from \(S_n^t\) by replacing each vertex from \(S_n^t\) by a copy of \(K_n\) and adding some special edges between these copies of \(K_n\). Let \(G\) be a graph. Partition \((V_0,V_1,V_2)\) of \(V(G)\) is a Roman partition of \(G\) if every vertex from \(V_0\) has a neighbor in \(V_2\) and the weight of this partition is \(f(V_0,V_1,V_2)=|V_1|+2|V_2|\). The Roman domination number \(\gamma_R(G)\) is then the minimum weight \(f(V_0,V_1,V_2)\) over all Roman partitions \((V_0,V_1,V_2)\). Similarly, a partition \((V_0,V_1,V_2,V_3)\) of \(V(G)\) is a double Roman partition of \(G\) if every vertex from \(V_0\) has a neighbor in \(V_3\) or two neighbors in \(V_2\) and every vertex from \(V_1\) has a neighbor in \(V_2\cup V_3\). The weight of this partition is \(f(V_0,V_1,V_2,V_3)=|V_1|+2|V_2|+3|V_3|\). The double Roman domination number \(\gamma_{dR}(G)\) is then the minimum weight \(f(V_0,V_1,V_2,V_3)\) over all double Roman partitions \((V_0,V_1,V_2,V_3)\). The author introduced a dominating set of \(S_n^k\) that yields a Roman and doubly Roman partition of \(S_n^k\) of minimum weight and this settles \(\gamma_{R}(S_n^k)\) and \(\gamma_{dR}(S_n^k)\).