On the outer-independent double Italian domination number
Abstract
An outer-independent Italian dominating function (OIIDF) on a graph G is a function f : V(G)→{0, 1, 2} such that every vertex v ∈ V(G) with f(v)=0 has at least two neighbors assigned 1 under f or one neighbor w with f(w)=2, and the set {u ∈ V(G)|f(u)=0} is independent. An outer-independent double Italian dominating function (OIDIDF) on a graph G is a function f : V(G)→{0, 1, 2, 3} such that if f(v)∈{0, 1} for a vertex v ∈ V(G), then ∑u ∈ N[v]f(u)≥3 and the set {u ∈ V(G)|f(u)=0} is independent. The weight of an OIIDF (respectively, OIDIDF) f is the value w(f)=∑v ∈ V(G)f(v). The minimum weight of an OIIDF (respectively, OIDIDF) on a graph G is called the outer-independent Italian (respectively, outer-independent double Italian) domination number of G. We characterize all trees T with outer-independent double Italian domination number twice the outer-independent Italian domination number. We also present lower bounds on the outer-independent double Italian domination number of a connected graph G in terms of the order, minimum and maximum degrees.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.2
References
H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Outer independent double Roman domination, Appl. Math. Comput. 364 (2020), ID: 124617.
F. Azvin and N. Jafari Rad, Bounds on the double Italian domination number of a graph, Discuss. Math. Graph Theory (to appear), doi:10.7151/dmgt.2330.
F. Azvin, N. Jafari Rad and L. Volkmann, Bounds on the outer-independent double Italian domination number, Comm. Combin. Optim. 6 (2021), 123–136.
R.A. Beeler, T.W. Haynes, S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
M. Benatallah, Outer-independent double Italian domination in graphs, Manuscript (2021).
M. Chellali, T. Haynes, S.T. Hedetniemi, A. McRae, Roman domination, Discrete Appl. Math. 204 (2016), 22–28.
M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Roman domination in graphs, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Eds. (Springer, 2020) 365–409. doi:10.1007/978-3-030–51117-3-11
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, 2021).
M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), 966–984.
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. (to appear).
M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, The Roman domatic problem in graphs and digraphs: A Survey, Discuss. Math. Graph Theory (2020), doi:10.7151/dmgt.2313.
E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), 11–22.
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.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York (1998).
M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017), 557–564.
N. Jafari Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5(1) (2017), 1–6.
W. Klostermyer and G. MacGillivray, Roman, Italian, and 2-domination, J. Combin. Math. Combin. Comput. 108 (2019), 125–146.
D.A. Mojdeh and L. Volkmann, Roman {3}–domination (double Italian domination), Discrete Appl. Math. 283 (2020), 555–564.
A. Poureidi, Total Roman domination for proper interval graphs, Electron. J. Graph Theory Appl. 8(2) (2020), 401–413.
L. Volkmann, Remarks on the outer-independent double Italian domination number, Opuscula Math. 41, no. 2 (2021), 259–268.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.