×

Global triple Roman dominating function. (English) Zbl 1490.05202

A triple Roman dominating function (TRD-function) of a graph \(G\) is a function \(f: V(G) \rightarrow \{0, 1, 2, 3, 4\}\) such that if \(f(v) < 3\), then \(f(AN[v]) \ge |AN(v)| + 3\), where \(AN(v)\) is the set of neighbors of \(v\) assigned a non-zero value under \(f\). The minimum weight of a TRD-function on \(G\) is the triple Roman domination number of \(G\), denoted by \(\gamma_{[3R]}(G)\). A global triple Roman dominating function is a TRD-function for both \(G\) and its complement; the global triple Roman domination number is denoted by \(\gamma_{g[3R]}(G)\). It is proved that the global triple Roman dominating problem is NP-complete for bipartite and chordal graphs. Numerous bounds on \(\gamma_{[3R]}(G)\) and \(\gamma_{g[3R]}(G)\) are given and relations between them studied. For instance, if the diameter of \(G\) is at least \(6\) or its radius is \(4\) or \(5\), then \(\gamma_{[3R]}(G) = \gamma_{g[3R]}(G)\), while if \(G\) is triangle-free, then \(\gamma_{g[3R]}(G) \le \gamma_{[3R]}(G) + 4\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI

References:

[1] Abdollahzadeh Ahangar, H., On the global Roman domination number in graphs, Iran. J. Sci. Technol. Trans. A Sci., 13, 157-164 (2016) · Zbl 1382.05051
[2] Abdollahzadeh Ahangar, H.; Alvarez, M. P.; Chellali, M.; Sheikholeslami, S. M.; Valenzuela-Tripodoro, J. C., Triple Roman domination in graphs, Appl. Math. Comput., 391, 13 (2021), 125444 · Zbl 1462.05266
[3] Abdollahzadeh Ahangar, H.; Amjadi, J.; Chellali, M.; Nazari-Moghaddam, S.; Sheikholeslami, S. M., Total Roman reinforcement in graphs, Discuss. Math. Graph Theory, 397, 787-803 (2019) · Zbl 1415.05128
[4] Abdollahzadeh Ahangar, H.; Bahramandpour, A.; Sheikholeslami, S. M.; Soner, N. D.; Tahmasbzadehbaee, Z.; Volkmann, L., Maximal Roman domination numbers in graphs, Utilitas Math., 103, 245-258 (2017) · Zbl 1373.05133
[5] Amjadi, J.; Sheikholeslami, S. M.; Volkmann, L., Global rainbow domination in graphs, Miskolc Math. Notes, 17, 749-759 (2016) · Zbl 1389.05119
[6] Arumugam, S.; Hamid, I. S.; Karuppasamy, K., Fractional global domination in graphs, Discuss. Math. Graph Theory, 30, 33-44 (2010) · Zbl 1214.05100
[7] Atapour, M.; Norouzian, S.; Sheikholeslami, S. M., Global minus domination in graphs, Trans. Comb., 3, 35-44 (2014) · Zbl 1463.05393
[8] Atapour, M.; Sheikholeslami, S. M.; Volkmann, L., Global Roman domination in graphs, Graphs Combin., 31, 813-825 (2015) · Zbl 1318.05049
[9] Beeler, R. A.; Haynes, T. W.; Hedetniemi, S. T., Double Roman domination, Discrete Appl. Math., 211, 23-29 (2016) · Zbl 1348.05146
[10] Cockayne, E. J.; Dreyer, P. A.; Hedetniemi, S. M.; Hedetniemi, S. T., Roman domination in graphs, Discrete Math., 278, 1-3, 11-22 (2004) · Zbl 1036.05034
[11] Delić, D.; Wang, C., The global connected domination in graphs, Ars Combin., 114, 105-110 (2014) · Zbl 1324.05139
[12] M. Hajjari, H. Abdollahzadeh Ahangar, R. Khoeilar, Z. Shao, S.M. Sheikholeslami, An upper bound on triple Roman domination. J. Comb. Math. Comb. Comput. (in press). · Zbl 07812865
[13] Hajjari, M.; Abdollahzadeh Ahangar, H.; Khoeilar, R.; Shao, Z.; Sheikholeslami, S. M., New bounds on the triple Roman domination number of graphs, J. Math., 2022, 5 (2022), 9992618
[14] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker, Inc.: Marcel Dekker, Inc. New York · Zbl 0890.05002
[15] Jakkepalli, P. K.; Arumugam, S.; Khandelwal, H.; V. S. Reddy, P., Algorithmic aspects of certified domination in graphs, Commun. Comb. Optim., 7, 247-255 (2022) · Zbl 1524.05215
[16] Kulli, V. R.; Janakiram, B., The total global domination number of a graph, India J. Pure Appl. Math., 27, 537-542 (1996) · Zbl 0853.05050
[17] Sampathkumar, E., The global domination number of a graph, J. Math. Phys. Sci., 23, 377-385 (1989) · Zbl 0729.05045
[18] Zverovich, V.; Poghosyan, A., On roman global and restrained domination in graphs, Graphs Combin., 27, 755-768 (2011) · Zbl 1234.05180
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.