Bounds on the outer-independent double Italian domination number

Document Type : Original paper

Authors

1 Shahed University

2 RWTH Aachen University

Abstract

An outer-independent double Italian dominating function (OIDIDF) on a graph $G$ with vertex set $V(G)$ is a function $f:V(G)\longrightarrow \{0,1,2,3\}$ such that if $f(v)\in\{0,1\}$ for a vertex $v\in V(G)$ then $\sum_{u\in N[v]}f(u)\geq3$, and the set $ \{u\in V(G)|f(u)=0\}$ is independent. The weight of an OIDIDF $f$ is the value $w(f)=\sum_{v\in V(G)}f(v)$. The minimum weight of an OIDIDF on a graph $G$ is called the outer-independent double Italian domination number $\gamma_{oidI}(G)$ of $G$. We present sharp lower bounds for the outer-independent double Italian domination number of a tree in terms of diameter, vertex covering number and the order of the tree.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M. Chellali, and V. Samodivkin, Outer independent Roman dominating functions in graphs, Int. J. Computer Math. 94 (2017), no. 12, 2547–2557.
[2] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Outer independent double Roman domination, Appl. Math. Compu. 364 (2020), ID: 124617.
[3] F. Azvin and N. Jafari Rad, Bounds on the double Italian domination number of a graph, Discuss. Math. Graph Theory, (in press).
[4] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[5] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A. McRae, Roman ${2}$-domination, Discrete Appl. Math. 204 (2016), 22–28.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on roman domination parameters in directed graphs, AKCE J. Graphs Combin., (in press).
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, J. Combin. Math. Comb. Comput., (to appear).
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, In: Topics in Domination in Graphs, Eds. T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Springer International Publishing, 2020.
[9] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, In: Structures of Domination in Graphs, Eds. T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Springer International Publishing, 2020.
[10] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[11] W. Fan, A. Ye, F. Miao, Z. Shao, V. Samodivkin, and S.M. Sheikholeslami, Outer-independent Italian domination in graphs, IEEE Access 7 (2019), 22756–22762.
[12] J.F. Fink, M.S. Jacobson, L.F. Kinch, and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985), no. 4, 287–293.
[13] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39.
[14] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[15] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017), 557–564.
[16] W. Klostermeyer and G. MacGillivray, Roman, Italian, and 2-domination, J. Combin. Math. Combin. Comput. 108 (2019), 125–146.
[17] D.A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math. 283 (2020), 555–564.
[18] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982), no. 1, 23–32.
[19] A. Poureidi and N. Jafari Rad, On algorithmic complexity of double Roman domination, Discrete Appl. Math. 285 (2020), 539–551.
[20] A. Poureidi and N. Jafari Rad, On the algorithmic complexity of Roman {2}-domination (Italian domination), Iran J. Sci. Technol. Trans. Sci 44 (2020), 791–799.
[21] Z. Shao, D.A. Mojdeh, and L. Volkmann, Total Roman ${3}$-domination in graphs, Symmetry 12 (2020), no. 2, ID: 268.
[22] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), no. 1, 71–77.
 
Communications in Combinatorics and Optimization
Volume 6, Issue 1
June 2021
Pages 123-136

Files

Share

How to cite

Statistics