×

Independent Roman domination and 2-independence in trees. (English) Zbl 1393.05194

Summary: Let \(G = (V, E)\) be a simple graph with vertex set \(V\) and edge set \(E\). A Roman dominating function on a graph \(G\) is a function \(f : V(G) \rightarrow \{0, 1, 2 \}\) satisfying the condition that every vertex \(u\) for which \(f(u) = 0\) is adjacent to at least one vertex \(v\) for which \(f(v) = 2\). A Roman dominating function \(f\) is called an independent Roman dominating function if the set of all vertices with positive weights is an independent set. The weight of an independent Roman dominating function \(f\) is the value \(f(V(G)) = \sum_{u \in V(G)} f(u)\). The independent Roman domination number of \(G\), denoted by \(i_R(G)\), is the minimum weight of an independent Roman dominating function on \(G\). A subset \(S\) of \(V\) is a 2-independent set of \(G\) if every vertex of \(S\) has at most one neighbor in \(S\). The maximum cardinality of a 2-independent set of \(G\) is the 2-independence number \(\beta_2(G)\). These two parameters are incomparable in general, however, we show that for any tree \(T\), \(\beta_2(T) \geq i_R(T)\) and we characterize all trees attaining the equality.

MSC:

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

References:

[1] Ahangar, H. Abdollahzadeh; Chellali, M.; Samodivkin, Vladimir, Outer independent Roman dominating functions in graphs, Int. J. Comput. Math., 94, 2547-2557, (2017) · Zbl 1391.05190
[2] Ahangar, H. Abdollahzadeh; Haynes, T. W.; Valenzuela-Tripodoro, J. C., Mixed Roman domination in graphs, Bull. Malays. Math. Sci. Soc., 40, 1443-1454, (2017) · Zbl 1386.05129
[3] Ahangar, H. Abdollahzadeh; Khaibari, M., Graphs with large Roman domination number, Malays. J. Math. Sci., 11, 71-81, (2017) · Zbl 1527.05132
[4] Adabi, M.; Targhi, E. Ebrahimi; Rad, N. Jafari; Moradi, M. Saied, Properties of independent Roman domination in graphs, Australas. J. Comb., 52, 11-18, (2012) · Zbl 1251.05116
[5] Chellali, M.; Favaron, O.; Hansberg, A.; Volkmann, L., \(k\)-domination and \(k\)-independence in graphs: A survey, Graphs Combin., 28, 1-55, (2012) · Zbl 1234.05174
[6] Chellali, M.; Haynes, T. W.; Hedetniemi, S. T., Lower bounds on the Roman and independent Roman domination numbers, Appl. Anal. Discrete Math., 10, 65-72, (2016) · Zbl 1461.05154
[7] Chellali, M.; Rad, N. J., Trees with independent Roman domination number twice the independent domination number, Discrete Math. Algorithms Appl., 7, 8, (2015) · Zbl 1331.05167
[8] Chellali, M.; Rad, N. J., A note on the independent Roman domination in unicyclic graphs, Opuscula Math., 32, 715-718, (2012) · Zbl 1259.05127
[9] 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
[10] Dehgardi, N., Mixed Roman domination and 2-independence in trees, Commun. Comb. Optim., 3, 79-91, (2018) · Zbl 1394.05086
[11] Favaron, O.; Karami, H.; Khoeilar, R.; Sheikholeslami, S. M., On the Roman domination number of a graph, Discrete Math., 309, 3447-3451, (2009) · Zbl 1191.05071
[12] Fink, J. F.; Jacobson, M. S., Graph Theory with Applications to Algorithms and Computer Science, On \(n\)-domination, \(n\)-dependence and forbidden subgraphs, 301-311, (1985), John Wiley and Sons, New York · Zbl 0573.05050
[13] Liu, C.-H.; Chang, G. J., Roman domination on \(2\)-connected graphs, SIAM J. Discrete Math., 26, 193-205, (2012) · Zbl 1245.05100
[14] Liu, C.-H.; Chang, G. J., Upper bounds on Roman domination numbers of graphs, Discrete Math., 312, 1386-1391, (2012) · Zbl 1237.05154
[15] Liu, C.-H.; Chang, G. J., Roman domination on strongly chordal graphs, J. Combin. Optim., 26, 608-619, (2013) · Zbl 1282.90217
[16] Mobaraky, B. P.; Sheikholeslami, S. M., Bounds on Roman domination numbers of a graph, Mat. Vesnik, 60, 247-253, (2008) · Zbl 1274.05359
[17] Pavlič, P.; Žerovnik, J., Roman domination number of the Cartesian products of paths and cycles, Electron. J. Combin., 19, 3, 37, (2012) · Zbl 1252.05167
[18] ReVelle, C. S.; Rosing, K. E., Defendens imperium romanum: A classical problem in military strategy, Amer. Math. Monthly, 107, 585-594, (2000) · Zbl 1039.90038
[19] Stewart, I., Defend the Roman empire!, Sci. Amer., 281, 136-139, (1999)
[20] West, D. B., Introduction to Graph Theory, (2001), Prentice Hall, USA
[21] Yero, I. G.; Rodríguez-Velázquez, J. A., Roman domination in Cartesian product graphs and strong product graphs, Appl. Anal. Discrete Math., 7, 262-274, (2013) · Zbl 1340.05204
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.