On the Roman Domination Polynomials

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

References

[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.
[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.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 16 May 2023

Files

Share

How to cite

Statistics