Remarks on the restrained Italian domination number in graphs

Document Type : Short notes

Author

RWTH Aachen University

Abstract

Let $G$ be a graph with vertex set $V(G)$. An Italian dominating function (IDF) is a function $f:V(G)\longrightarrow \{0,1,2\}$ having the property that that $f(N(u))\geq 2$ for every vertex $u\in V(G)$ with $f(u)=0$, where $N(u)$ is the neighborhood of $u$. If $f$ is an IDF on $G$, then let $V_0=\{v\in V(G): f(v)=0\}$. A restrained Italian dominating function (RIDF) is an Italian dominating function $f$ having the property that the subgraph induced by $V_0$ does not have an isolated vertex. The weight of an RIDF $f$ is the sum $\sum_{v\in V(G)}f(v)$, and the minimum weight of an RIDF on a graph $G$ is the restrained Italian domination number. We present sharp bounds for the restrained Italian domination number, and we determine the restrained Italian domination number for some families of graphs.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M. Chellali, M. Hajjari, and S.M. Sheikholeslami, Further progress on the total Roman {2}-domination number of graphs, Bull. Iranian Math. Soc. (In press).
[2] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Total Roman {2}-dominating functions in graphs, Discuss. Math. Graph Theory (In press). 
[3] H. Abdollahzadeh Ahangar and S.R. Mirmehdipour, Bounds on the restrained Roman domination number of a graph, Commun. Comb. Optim. 1 (2016), no. 1, 75–82.
[4] F. Azvin and N. Jafari Rad, Bounds on the double Italian domination number of a graph, Discuss. Math. Graph Theory (In press).
[5] F. Azvin, N. Jafari Rad, and L. Volkmann, Bounds on the outer-independent double Italian domination number, Commun. Comb. Optim. 6 (2021), no. 1, 123–136.
[6] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A. MacRae, Roman {2}-domination, Discrete Appl. Math. 204 (2016), 22–28.
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, pp. 365–409.
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Comb. Comput. 151 (2020), 141–171.
[9] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.
[10] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2021, pp. 273–307.
[11] 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.
[12] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, and L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999), no. 1-3, 61–69.
[13] J.H. Hattingh and E.F. Joubert, Restrained and total restrained domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, 2020, pp. 129–150.
[14] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[15] D.A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math. 283 (2020), 555–564.
[16] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), no. 3, 175–177.
[17] R.L. Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Trans. Comb. 4 (2015), no. 1, 1–17.
[18] B. Samadi, M. Alishahi, I. Masoumi, and D.A. Mojdeh, Restrained Italian domination in graphs, RAIRO-Oper. Res. 55 (2021), no. 2, 319–332.
[19] F. Siahpour, H. Abdollahzadeh Ahangar, and S.M. Sheikholeslami, Some progress on the restrained Roman domination, Bull. Malays. Math. Sci. Soc. 44 (2021), no. 2, 733–751.
[20] L. Volkmann, Restrained double Italian domination in graphs, Commun. Comb. Optim. (In press).
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 183-191

Files

Share

How to cite

Statistics