Some Results for Roman Domination Number on Cardinal Product of Paths and Cycles

A. Klobučar   ; I. Puljić

Kragujevac Journal of Mathematics, Tome 38 (2014) no. 1, p. 83

Résumé

For a graph $G=(V,E)$, a Roman dominating function (RDF) is a function $f \colon V \to \{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 an RDF equals $w(f)=\sum_{v\in V}f(v)=|V_1|+2|V_2|$ where $V_i=\{v\in V: f(v)=i\}$, $i\in \{1,2\}$. An RDF for which $w(f)$ achieves its minimum is called a $\gamma_R$-function and its weight, denoted by $\gamma_R(G)$, is called the Roman domination number. In this paper we determine a lower and the upper bounds for $\gamma_R(P_m\times P_n)$ as well as the exact value of $\lim_{m,n\to \infty} \frac{\gamma_R(P_m\times P_n)}{mn}$ where $P_m\times P_n$ stands for the cardinal product of two paths. We also present some results concerning the cardinal product of two cycles $C_m\times C_n$ as well as the exact value of $\lim_{m,n\to \infty}\frac{\gamma_R(C_m\times C_n)}{mn}$.

Détail

Classification : 05C69 05C38
Keywords: Roman dominating function, Roman domination number $\gamma_R$, Cardinal product of paths, Cardinal product of cycles