路径笛卡尔乘积图的外独立罗马控制

Outer-Independent Roman Domination on Cartesian Product of Paths

中文关键词:  罗马控制  外独立罗马控制  笛卡尔乘积图  路径

英文关键词:Roman domination  outer-independent Roman domination  Cartesian product graphs  paths

中文摘要:

      图的外独立罗马控制起源于古罗马时期的防御策略:如果一个没有军队驻守的城市受到攻击,与其相邻的有两只军队驻守的城市可以派出一支军队去支援;任何两个没有军队驻守的城市不能相邻.图的外独立罗马控制是图论中一个很有吸引力的课题,其定义如下.给定一个图$G=(V,E)$, 函数$f: V(G)\rightarrow \{0,1,2\}$是一个外独立罗马控制函数(OIRDF)如果$f$满足:每个$f(v)=0$的顶点$v$都至少有一个顶点$u\in N(v)$满足$f(u)=2$,其中$N(v)$是$v$的开邻域; $V_0=\{v|f(v)=0\}$是独立集.外独立罗马控制函数的权重为$w(f) = \sum_{v\in V} f(v)$. $\min_f w(f)$ 是图$G$的外独立罗马控制数,记为$\gamma_{oiR}(G)$.本文研究了路径笛卡尔乘积图$P_{n}\Box P_{m}$的外独立罗马控制数.利用计算机程序,我们找到了可递归的外独立罗马控制函数并且给出了$\gamma_{oiR}(P_{n}\Box P_{m})$的上界.此外,我们证明了$\gamma_{oiR}(P_{n}\Box P_{m})~(n\le 3)$的下界等于上界.因此,我们最终得到了$n\le 3$时$\gamma_{oiR}(P_{n}\Box P_{m})$的精确值以及$n\ge 4$时$\gamma_{oiR}(P_{n}\Box P_{m})$的上界.

英文摘要:

      Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome, which is that if any city without an army is attacked, a neighboring city with two armies could mobilize an army to support it and any two cities that have no army cannot be adjacent. The outer-independent Roman domination on graphs is an attractive topic in graph theory, and the definition is described as follows. Given a graph $G = (V, E)$, a function $f: V (G) \rightarrow \{0, 1, 2\}$ is an outer-independent Roman dominating function (OIRDF) if $f$ satisfies that every vertex $v \in V$ with $f(v) = 0$ has at least one adjacent vertex $u \in N(v)$ with $f(u) = 2$, where $N(v)$ is the open neighborhood of $v$, and the set $V_0=\{v|f(v)=0\}$ is an independent set. The weight of an OIRDF $f$ is $w(f) = \sum_{v\in V} f(v)$. The value of $\min_f w(f)$ is the outer-independent Roman domination number of $G$, denoted as $\gamma_{oiR}(G)$. This paper is devoted to the study of the outer-independent Roman domination number of the Cartesian product of paths $P_{n}\Box P_{m}$. With the help of computer, we find some recursive OIRDFs and then we present an upper bound of $\gamma_{oiR}(P_{n}\Box P_{m})$. Furthermore, we prove the lower bound of $\gamma_{oiR}(P_{n}\Box P_{m})~(n\le 3)$ is equal to the upper bound. Hence, we achieve the exact value of $\gamma_{oiR}(P_{n}\Box P_{m})$ for $n\le 3$ and the upper bound of $\gamma_{oiR}(P_{n}\Box P_{m})$ for $n\ge 4$.