Nonnegative signed total Roman domination in graphs

Document Type : Original paper

Authors

1 Sirjan University of Technology, Sirjan 78137, Iran

2 RWTH Aachen University

Abstract

‎
Let G be a finite and simple graph with vertex set V(G). A nonnegative signed total Roman dominating function (NNSTRDF) on a graph G is a function f:V(G)→{−1,1,2} satisfying the conditions that (i) ∑x∈N(v)f(x)≥0 for each v∈V(G), where N(v) is the open neighborhood of v, and (ii) every vertex u for which f(u)=−1 has a neighbor v for which f(v)=2. The weight of an NNSTRDF f is ω(f)=∑v∈V(G)f(v). The nonnegative signed total Roman domination number γstRNN(G) of G is the minimum weight of an NNSTRDF on G. In this paper we initiate the study of the nonnegative signed total Roman domination number of graphs, and we present different bounds on γstRNN(G). We determine the nonnegative signed total Roman domination number of some classes of graphs. If n is the order and m is the size of the graph G, then we show that γstRNN(G)≥34(8n+1+1)−n and γstRNN(G)≥(10n−12m)/5. In addition, if G is a bipartite graph of order n, then we prove that γstRNN(G)≥324n+1−1)−n.

Keywords

References

[1] N. Dehgardi and L. Volkmann, Signed total Roman k-domination in directed graphs, Commun. Comb. Optim. 1 (2016), no. 2, 165–178.
[2] N. Dehgardi and L. Volkmann, Nonnegative signed edge domination in graphs, Kragujevac J. Math. 43 (2019), no. 1, 31–47.
[3] N. Dehgardi and L. Volkmann, Nonnegative signed Roman domination in graphs, J. Combin. Math. Combin. Comput. (to appear).
[4] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs, Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[5] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York,
1998.
[6] L. Volkmann, Signed total Roman domination in graphs, J. Comb. Optim. 32 (2016), no. 3, 855–871.
[7] L. Volkmann, Signed total Roman domination in digraphs, Discuss. Math. Graph Theory 37 (2017), no. 1, 261–272.
[8] L. Volkmann, Signed total Roman k-domination in graphs, J. Combin. Math. Combin. Comput. 105 (2018), 105–116.
Communications in Combinatorics and Optimization
Volume 5, Issue 2
December 2020
Pages 139-155

Files

Share

How to cite

Statistics