1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Bounds on the Double Italian Domination Number of a Graph

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1129 - 1137
Received: 30 Jan 2020
Accepted: 11 May 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

For a graph G, a Roman {3}-dominating function is a function f : V → {0, 1, 2, 3} having the property that for every vertex uV, if f(u) ∈ {0, 1}, then f(N[u]) ≥ 3. The weight of a Roman {3}-dominating function is the sum w(f) = f(V) = ΣvV f(v), and the minimum weight of a Roman {3}-dominating function is the Roman {3}-domination number, denoted by γ{R3}(G). In this paper, we present a sharp lower bound for the double Italian domination number of a graph, and improve previous bounds given in [D.A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math. 283 (2022) 555–564]. We also present a probabilistic upper bound for a generalized version of double Italian domination number of a graph, and show that the given bound is asymptotically best possible.

Keywords

MSC 2010

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

[2] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. McRae, Roman {2}-domination, Discrete Appl. Math. 204 (2016) 22–28. https://doi.org/10.1016/j.dam.2015.11.013 Search in Google Scholar

[3] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Combin. 17 (2020) 966–984.10.1016/j.akcej.2019.12.001 Search in Google Scholar

[4] 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

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

[6] 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

[7] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557–564. https://doi.org/10.1016/j.dam.2016.09.035 Search in Google Scholar

[8] W. Klostermeyer and G. MacGillivray, Roman, Italian, and 2-domination (J. Combin. Math. Combin. Comput.), to appear. Search in Google Scholar

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

[10] Z. Shao, D.A. Mojdeh and L. Volkmann, Total Roman {3}-domination in graphs, Symmetry 12 (2020) 1–15. https://doi.org/10.3390/sym12020268 Search in Google Scholar

[11] C.S. ReVelle and K.E. Rosing, Defendens Imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594. https://doi.org/10.1080/00029890.2000.12005243 Search in Google Scholar

[12] I. Stewart, Defend the Roman Empire!, Sci. Amer. 281 (1999) 136–139. https://doi.org/10.1038/scientificamerican1299-136 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo