فهرست نشریات علمی دسترسی آزاد ایران

A Roman dominating function on a graph $G = (V, E)$ is a function $f : V(G) → {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 weight of a Roman dominating function is the value $f(V) = \sum_{u∈V(G)}f(u)$. The minimum possible weight of a Roman dominating function on $G$ is called the Roman domination number of $G$ and is denoted by $\gamma_R(G)$. In this paper, and among some other results, we provide some bounds for the Roman domination number of the subdivision graph $S(G)$ of an arbitrary graph $G$. Also, we determine the exact value of $\gamma_R(S(G))$ when $G$ is $K_n$, $K_{r,s} or $K_{n_1,n_2,...,n_k}$.