Roman domination number of 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

A function $f:V\rightarrow \{0,1,2\}$ on a signed graph $S=(G,\sigma)$  where $G = (V,E)$ is a Roman dominating function(RDF) if $f(N[v]) = f(v) + \sum_{u \in N(v)} \sigma(uv)f(u) \geq 1$ for all $v\in V$ and for each vertex $v$ with $f(v)=0$ there is a vertex $u$ in $N^+(v)$ such that $f(u) = 2$. The weight of an RDF $f$ is given by $\omega(f) =\sum_{v\in V}f(v)$ and the minimum weight among all the RDFs on $S$ is called the Roman domination number $\gamma_R(S)$. Any RDF on $S$ with the minimum weight is known as a $\gamma_R(S)$-function. In this article we obtain certain bounds for $ \gamma_{R} $ and characterise the signed graphs attaining small values for $ \gamma_R. $

Keywords

Main Subjects

References

[1] B.D. Acharya, Domination and absorbance in signed graphs and digraphs. I: Foundations, J. Combin. Math. Combin. Comput. 84 (2013), 5–20.
[2] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[3] D. Cartwright and F. Harary, Structural balance: A generalization of Heider’s theory, Psychological Review 63 (1956), 277–293.
[4] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A. McRae, Roman {2}-domination, Discrete Appl. Math. 204 (2016), 22–28.
[5] 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.
[6] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953), no. 2, 143–146.
[7] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire–A new strategy, Discrete Math. 266 (2003), no. 6, 239–251.
[8] P. Jeyalakshmi, Domination in signed graphs, Discrete Math. Algorithms Appl. 13 (2020), no. 1, ID: 2050094.
[9] J. Joseph and M. Joseph, Roman domination in signed graphs, Commun. Comb. Optim. (In press).
[10] D.A. Mojdeh and L. Volkmann, Roman {3}-domination(double Italian domination), Discrete Appl. Math. 283 (2020), 555–564.
[11] I. Stewart, Defend the Roman Empire!, Scientific American 281 (1999), no. 6, 136–139.
[12] D. B. West, Introduction to Graph Theory, Prentice-Hall of India, 1999.
[13] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electro. J. Combin. 25 (2018), # DS8.
Communications in Combinatorics and Optimization
Volume 8, Issue 4
December 2023
Pages 759-766

Files

Share

How to cite

Statistics