Lower and upper bounds on independent double Roman domination in trees

M. Kheibari, Hossein Abdollahzadeh Ahangar, R. Khoeilar, S.M. Sheikholeslami


For a graph G = (V, E), a double Roman dominating function (DRDF) f : V → {0, 1, 2, 3} has the property that for every vertex v ∈ V with f(v)=0, either there exists a neighbor u ∈ N(v), with f(u)=3, or at least two neighbors x, y ∈ N(v) having f(x)=f(y)=2, and every vertex with value 1 under f has at least a neighbor with value 2 or 3. The weight of a DRDF is the sum f(V)=∑v ∈ Vf(v). A DRDF f is an independent double Roman dominating function (IDRDF) if the vertices with weight at least two form an independent set. The independent double Roman domination number idR(G) is the minimum weight of an IDRDF on G. In this paper, we show that for every tree T with diameter at least three, i(T)+iR(T)−(s(T))/2 + 1 ≤ idR(T)≤i(T)+iR(T)+s(T)−2, where i(T),iR(T) and s(T) are the independent domination number, the independent Roman domination number and the number of support vertex of T, respectively.


double Roman domination; independent double Roman dominating function; independent double Roman domination number

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.8


H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, and S. Nazari-Moghaddam and S.M. Sheikholeslami, Trees with double Roman domination number twice the domination number plus two, Iran. J. Sci. Technol. Trans. A Sci. (to appear)

H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 103 (2017), 245--258.

M. Adabi, E.E Targhi, N. Jafari Rad, and M.S. Moradi, Properties of independent Roman domination in graphs, Australas. J. Combin. 52 (2012), 11--18.

J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami, and L.

Volkmann, An upper bound on the double Roman domination number, J. Comb. Optim. 36 (2018), 81--89.

R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23--29.

E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J.Discrete Math. 23 (2009) 1575--1586.

M. Chellali and N. Jafari Rad, A note on the independent Roman domination in unicyclic graphs, Opuscula Math. 32 (2012), 715-718.

M. Chellali and N. Jafari Rad, Trees with independent Roman domination number twice the independent domination number, Discrete Math. Algorithms Appl. 7 (2015), 1550048.

E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), 11--22.

O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009), 3447--3451.

H.R. Maimani, M. Momeni, S. Nazari-Moghaddam, F. Rahimi Mahid, and S.M. Sheikholeslami, Independent double Roman domination in graphs, Bulletin of the Iranian Mathematical Society (to appear)

E.E Targhi, N. Jafari Rad, C.M. Mynhardt, and Y. Wu Properties of independent Roman domination in graphs, J. Combin. Math. Combin. Comput. 80 (2012), 351--365.

L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), 71--77.

X. Zhang, Z. Li, H. Jiang, and Z. Shao, Double Roman

domination in trees, Info. Prcess. Lett. 134 (2018), 31--34.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats