Document Type : Original paper

**Authors**

Shahed University

**Abstract**

A Roman dominating function (RDF) on a graph $G$ is a function $ f:V(G)\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of an RDF $f$ is the sum of the weights of the vertices under $f$. The Roman domination number, $\gamma_R(G)$ of $G$ is the minimum weight of an RDF in $G$. The Roman domination polynomial of a graph $G$ of order $n$ is the polynomial $RD(G,x)=\sum_{i=\gamma_R(G)}^{2n} d_R(G,i) x^{i}$, where $d_R(G,i)$ is the number of RDFs of $G$ with weight $i$. In this paper we prove properties of Roman domination polynomials and determine $RD(G,x)$ in several classes of graphs $G$ by new approaches. We also present bounds on the number of all Roman domination polynomials in a graph.

**Keywords**

**Main Subjects**

[1] S. Alikhani, The domination polynomial of a graph at -1, Graphs Comb. 29 (2013), no. 5, 1175–1181.

[2] S. Alikhani and N. Jafari, Some new results on the total domination polynomial of a graph, Ars Combin. 149 (2020), 185–197.

[3] S. Alikhani and Y.H. Peng, Dominating sets and domination polynomials of paths, Int. J. Math. Math. Sci. 2009 (2009), Article ID: 542040.

[4] S. Alikhani and Y.H. Peng, Introduction to domination polynomial of a graph, Ars Combin. 114 (2014), 257–266.

[5] R.A. Brualdi, Introductory Combinatorics, Pearson India, 2019.

[6] 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.

[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.

[8] 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.

[9] 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.

[10] G. Deepak, A. Alwardi, and M.H. Indiramma, Roman domination polynomial of cycles, Int. J. Math. Combin. 3 (2021), 86–97.

[11] G. Deepak, A. Alwardi, and M.H. Indiramma, Roman domination polynomial of paths, Palestine J. Math. 11 (2022),

no. 2, 439–448.

no. 2, 439–448.

[12] D. Gangabylaiah, M.H. Indiramma, N.D. Soner, and A. Alwardi, On the Roman domination polynomial of graphs, Bull. Int. Math. Virtual Inst. 11 (2021), no. 2, 355–365.

[13] T.W. Haynes, S.T. Hedetniemi, and P.J. Salter, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.

[14] D.A. Mojdeh and A.S. Emadi, Connected domination polynomial of graphs, Fasc. Math, 60 (2018), no. 1, 103–121.

[15] D.A. Mojdeh and A.S. Emadi, Hop domination polynomial of graphs, J. Discrete Math. Sci. Crypt. 23 (2020), no. 4, 825–840.

September 2024

Pages 595-605