Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

Double Roman and Double Italian Domination

Accepted: 15 Feb 2021
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

Let G be a graph with vertex set V (G). A double Roman dominating function (DRDF) on a graph G is a function f : V (G) −→ {0, 1, 2, 3} that satisfies the following conditions: (i) If f(v) = 0, then v must have a neighbor w with f(w) = 3 or two neighbors x and y with f(x) = f(y) = 2; (ii) If f(v) = 1, then v must have a neighbor w with f(w) ≥ 2. The weight of a DRDF f is the sum ΣvV(G)f(v). The double Roman domination number equals the minimum weight of a double Roman dominating function on G. A double Italian dominating function (DIDF) is a function f : V (G) → {0, 1, 2, 3} having the property that f(N[u]) ≥ 3 for every vertex uV (G) with f(u) ∈ {0, 1}, where N[u] is the closed neighborhood of v. The weight of a DIDF f is the sum Σ ΣvV(G)f(v), and the minimum weight of a DIDF in a graph G is the double Italian domination number. In this paper we first present Nordhaus-Gaddum type bounds on the double Roman domination number which improved corresponding results given in [N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019) 41–53]. Furthermore, we establish lower bounds on the double Roman and double Italian domination numbers of trees.

MSC 2010

[1] H.A. Ahangar, M. Chellali and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017) 1–7. doi:10.1016/j.dam.2017.06.01410.1016/j.dam.2017.06.014Search in Google Scholar

[2] 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. doi:10.1007/s10878-018-0286-610.1007/s10878-018-0286-6Search in Google Scholar

[3] F. Azvin and N. Jafari Rad, Bounds on the double Italian domination number of a graph, Discuss. Math. Graph Theory, in press. doi:10.7151/dmgt.233010.7151/dmgt.2330Search in Google Scholar

[4] F. Azvin, N. Jafari Rad and L. Volkmann, Bounds on the outer-independent double Italian domination number, Commun. Comb. Optim. 6 (2021) 123–136.Search in Google Scholar

[5] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29. doi:10.1016/j.dam.2016.03.01710.1016/j.dam.2016.03.017Search in Google Scholar

[6] 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_1110.1007/978-3-030-51117-3_11Search in Google Scholar

[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, in: Structures of Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Eds. (Springer, 2021).10.1007/978-3-030-51117-3_11Search in Google Scholar

[8] 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. doi:10.1016/j.akcej.2019.12.00110.1016/j.akcej.2019.12.001Search in Google Scholar

[9] 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.Search in Google Scholar

[10] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22. doi:10.1016/j.disc.2003.06.00410.1016/j.disc.2003.06.004Search in Google Scholar

[11] M. Hajibaba and N. Jafari Rad, A note on the Italian domination number and double Roman domination number in graphs, J. Combin. Math. Combin. Comput. 109 (2019) 169–183.Search in Google Scholar

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).Search in Google Scholar

[13] N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019) 41–53. doi:10.7151/dmgt.206910.7151/dmgt.2069Search in Google Scholar

[14] R. Khoeilar, H. Karami, M. Chellali and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019) 159–167. doi:10.1016/j.dam.2019.06.01810.1016/j.dam.2019.06.018Search in Google Scholar

[15] D.A. Mojdeh and L. Volkmann, Roman {3}–domination (double Italian domination), Discrete Appl. Math. 283 (2020) 555–564. doi:10.1016/j.dam.2020.02.00110.1016/j.dam.2020.02.001Search in Google Scholar

[16] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177. doi:10.2307/230665810.2307/2306658Search in Google Scholar

[17] Z. Shao, D.A. Mojdeh and L. Volkmann, Total Roman {3}-domination, Symmetry 12 (2020) 268. doi:10.3390/sym1202026810.3390/sym12020268Search in Google Scholar

• A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD