Roman domination in signed graphs

Document Type : Original paper

Authors

1 CHRIST(Deemed to be University), Bangalore

2 CHRIST(Deemed to be University) Hosur Road Bangalore-560029

Abstract

Let $S = (G,\sigma)$ be a signed graph. A function $f: V \rightarrow \{0,1,2\}$ is a Roman dominating function on $S$ if $(i)$ for each $v \in V,$ $f(N[v]) = f(v) + \sum_{u \in N(v)} \sigma(uv ) f(u) \geq 1$ and $(ii)$ for each vertex $ v $ with $ f(v) = 0 $ there exists a vertex $u \in N^+(v)$ such that $f(u) = 2.$ In this paper we initiate a study on Roman dominating function on signed graphs. We characterise the signed paths, cycles and stars that admit a Roman dominating function.

Keywords

Main Subjects

References

[1] H. Abdolahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, and S.M. Sheikholeslami, Total Roman reinforcement in graphs, Discuss. Math. Graph Theory 397 (2019), no. 4, 787–803.
[2] H. Abdollahzadeh Ahangar, M. P. ´Alvarez, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Triple Roman domination in graphs, Appl. Math. Comput. 391 (2021), ID: 125444.
[3] H. Abdollahzadeh Ahangar, A. Bahremandpour, S.M. Sheikholeslami, N.D. Soner, Z. Tahmasbzadehbaee, and L. Volkmann, Maximal Roman domination numbers in graphs, Util. Math. 103 (2017), 245–258.
[4] B. D. Acharya, Minus domination in signed graphs, J. Comb. Inf. Syst. Sci. 37 (2012), no. 2-4, 333–358.
[5] B.D. Acharya, Domination and absorbance in signed graphs and digraphs, J. Comb. Math. Comb. Comput. 84 (2013), 5–20.
[6] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete App. Math. 211 (2016), 23–29.
[7] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A. McRae, Roman {2}-domination, Discrete App. Math. 204 (2016), 22–28.
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, p. 365–409.
[9] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, eds.), Springer, Berlin/Heidelberg, 2021, p. 273–307.
[10] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[11] F. Harary, On the notion of balance of a signed graph, Mich. Math. J. 2 (1953), no. 2, 143–146.
[12] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Models of domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, p. 13–30.
[13] T.W. Haynes, S.T. Hedetniemi, and P.J. Salter, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[14] P. Jeyalakshmi, Domination in signed graphs, Discrete Math. Algorithms Appl. 13 (2020), no. 1, ID: 2050094.
[15] H.B. Walikar, S.V. Motammanavar, and B.D. Acharya, Signed domination in signed graph, J. Comb. Inf. Syst. Sci. 40 (2015), no. 1-4, 107–128.
[16] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Comb. 1000 (2018), 1–524.
Communications in Combinatorics and Optimization
Volume 8, Issue 2
June 2023
Pages 349-358

Files

Share

How to cite

Statistics