Roman domination value in graphs

Document Type : Original paper

Authors

1 Department of Mathematics, D.B. Jain College, Chennai 600 097, Tamil Nadu, India

2 Department of Mathematics, Sri Sairam Engineering College, Chennai 600 044, Tamil Nadu, India

Abstract

For a graph G=(V,E), a set SV is a \textit{dominating set} if every vertex in VS has a neighbour in S.  The \textit{domination number}, denoted by γ(G), is the minimum cardinality of a dominating set in G and a dominating set of minimum cardinality is called a \textit{γ(G)-set}. Cockayne et al. defined a \textit{Roman dominating function} (RDF) on a graph G=(V,E) to be a function f:V{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. The \textit{Roman domination number}, denoted by γR(G), is the minimum weight of an RDF in G. An RDF of weight γR(G) is called a \textit{γR(G)-function}. Eunjeong Yi introduced the \textit{domination value of v}, denoted by DVG(v), to be the number of γ(G)-sets to which v belongs. In this paper, we extend the idea of domination value to Roman domination. For a vertex vV, we define the \textit{Roman domination value}, denoted by RG(v),  as RG(v)=fFf(v), where F denote the set of  all γR(G)-functions.  We also study some basic properties of Roman domination value of vertices for a given graph and determine the Roman domination value for the  vertices of a complete k-partite graph.

Keywords

Main Subjects


[1] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, Chapman & Hall London, 1996.
[2] 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 Cham, 2020, pp. 365–409.
[3] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Combin. 17 (2020), no. 3, 365–409.  https://doi.org/10.1016/j.akcej.2019.12.001
[4] 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.  https://doi.org/10.1016/j.disc.2003.06.004
[5] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013.
[6] T.W. Haynes, S. Hedetniemi, and P. Slater, Domination in Graphs: Volume 2: Advanced Topics, CRC Press, 2017.
[7] C.X. Kang, Total domination value in graphs, Util. Math. 95 (2014), 263–279.
[8] C.M. Mynhardt, Vertices contained in every minimum dominating set of a tree, J. Graph Theory 31 (1999), no. 3, 163–177.
[9] P.R.L. Pushpam and S. Padmapriea, Global Roman domination in graphs, Discrete Appl. Math. 200 (2016), 176–185. https://doi.org/10.1016/j.dam.2015.07.014
[10] P.R.L. Pushpam and S. Padmapriea, On total Roman domination in graphs, Theoretical Computer Science and Discrete Mathematics (Cham) (S. Arumugam, J. Bagga, L.W. Beineke, and B.S. Panda, eds.), Springer International Publishing, 2017, p. 326–331.
[11] P.R.L. Pushpam and S. Padmapriea, Forcing Roman domination in graphs, Congr. Numer. 25 (2018), no. 6–7, 441–453.
[12] P.J. Slater, The Hedetniemi number of a graph, Congr. Numer. 139 (1999), 65–75.
[13] I. Stewart, Defend the Roman Empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[14] E. Yi, Domination value in graphs, Contrib. Discrete Math. 7 (2012), no. 2, 30–43.
[15] E. Yi, Domination value in P2 × Pn and P2 × Cn, J. Combin. Math. Combin. Comput. 82 (2012), 59–75.