Restrained double Italian domination in graphs

Document Type : Original paper

Author

RWTH Aachen University

Abstract

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

Keywords

Main Subjects

References

[1] F. Azvin and N. Jafari Rad, Bounds on the double Italian domination number of a graph, Discuss. Math. Graph Theory (in press).
[2] 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.
[3] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A. MacRae, Roman {2}-domination, Discrete Appl. Math. 204 (2016), 22–28.
[4] 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.
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020), 141–171.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[13] D.A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math. 283 (2020), 555–564.
[14] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), no. 3, 175–177.
[15] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982), no. 1, 23–32.
[16] Z. Shao, D.A. Mojdeh, and L. Volkmann, Total Roman {3}-domination in graphs, Symmetry 12 (2020), no. 2, Article ID: 268.
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 1-11

Files

Share

How to cite

Statistics