Doost Ali Mojdeh, Ali Parsian, Iman Masoumi

Strong Roman Domination Number of Complementary Prism Graphs

Let G = (V, E) be a simple graph with vertex set V = V(G), edge set E = E(G) and from maximumdegree ∆ = ∆(G). Also let f : V → {0, 1, ...,d ∆ 2e + 1} be a function that labels the vertices of G. Let Vi ={v ∈ V : f(v) = i} for i = 0, 1 and let V2 = V − (V0 SV1) = {w ∈ V : f(w) ≥ 2}. A function f is calleda strong Roman dominating function (StRDF) for G, if every v ∈ V0 has a neighbor w, such that w ∈ V2 andf(w) ≥ 1 + d 1 2 |N(w) TV0|e. The minimum weight, ω(f) = f(V) = Σv∈V f(v), over all the strong Roman dominatingfunctions of G, is called the strong Roman domination number of G and we denote it by γS tR(G). An StRDF ofminimum weight is called a γS tR(G)-function. Let G be the complement of G. The complementary prism GG ofG is the graph formed from the disjoint union G and G by adding the edges of a perfect matching between thecorresponding vertices of G and G. In this paper, we investigate some properties of Roman, double Roman andstrong Roman domination number of GG.

PDF

___

[1] Alhashim, A., Desormeaux, W.J., Haynes, T.W., Roman domination in complementary prisms, Australasian journal of combinatorics, 68(2)(2017), 218–228.
[2] Alvarez-Ruiz, M.P., Mediavilla-Gradolph, T., Sheikholeslami, S.M., Valenzuela-Tripodoro, J.C., Yero, I.G., On the strong Roman domination number of graphs, Discrete Applied Mathematics, 231(2017), 44–59.
[3] Bermudo, S., Fernau, H., Sigarreta, J.M., The differential and the Roman domination number of a graph, Applicable Analysis and Discrete Mathematics, 8(2014), 155–171.
[4] Beeler, R.A., Haynesa, T.W., Hedetniemi, S.T., Double Roman domination, Discrete Applied Mathematics, 211(2016), 23–29.
[5] Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T., Roman domination in graphs, Discrete Mathematics, 278(2004), 11–22.
[6] Chambers, E.W., Kinnersley, B., Prince, N. , West, D.B., Extermal problems for Roman domination, SIAM J. Discret Mathematics, 23(3)(2009), 1575–1586.
[7] Desormeaux, W.J., Haynes, T.W., Henning, M.A., Domination parameters of a graph and it´s complement, Discussiones Mathematicae Graph Theory, 38(2018), 203–215.
[8] Gongora, J.A., Independent Domination in Complementary Prisms, Masters Thesis, East Tennessee State University, 2009.
[9] Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[10] Haynes, T.W., Holmes, K.R.S., Koessler, D.R., Sewell, L., Locating-Domination in Complementary Prisms of Paths and Cycles, Congressus Numerantium, 199(2009), 45–55.
[11] Haynes, T.W., Henning, M.A., Slater, P.J., van der Merwe, L.C. , The complementary product of two graphs, Bulletin of the Institute of Combinatorics and its Applications, 51(2007), 21–30.
[12] Haynes, T.W., Henning, M.A., van der Merwe, L.C., Domination and total domination in complemantary prisms, Journal of Combinatorial Optimization, 18(2009), 23–37.
[13] Janseana, P., Ananchuen, N., Matching extension in complementary prism of regular graphs, Italian Journal of Pure and Applied Mathematics, 37(2017), 553–564.
[14] Lewis, J.R., Differentials of Graphs, Masters Thesis, East Tennessee State University, 2004.
[15] Mojdeh, D.A., Parsian, A., Masoumi, I., Characterization of double Roman trees, to appear in Ars Combinatoria, (2018).
[16] West, D.B., Introduction to Graph theory, Second edition, Prentice Hall, USA, 2001.