Outer-Independent Roman Domination on Cartesian Product of Paths

作     者：Junzhe GUO Hong GAO Yuansheng YANG Junzhe GUO;Hong GAO;Yuansheng YANG

作者机构：College of Science Dalian Maritime University School of Computer Science and Technology Dalian University of Technology 

出 版 物：《Journal of Mathematical Research with Applications》 (数学研究及应用(英文))

年 卷 期：2025年第45卷第1期

页      面：11-19页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Roman domination outer-independent Roman domination Cartesian product graphs paths 

摘      要：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) → {0, 1, 2} is an outer-independent Roman dominating function(OIRDF) if f satisfies that every vertex v ∈ V with f(v) = 0 has at least one adjacent vertex u ∈ N(v) with f(u) = 2,where N(v) is the open neighborhood of v, and the set V0 = {v|f(v) = 0} is an independent set. The weight of an OIRDF f is w(f) =∑v∈Vf(v). The value of minf w(f) is the outerindependent Roman domination number of G, denoted as γoiR(G). This paper is devoted to the study of the outer-independent Roman domination number of the Cartesian product of paths Pn□Pm. With the help of computer, we find some recursive OIRDFs and then we present an upper bound of γoiR(Pn□Pm). Furthermore, we prove the lower bound of γoiR(Pn□Pm)(n ≤ 3)is equal to the upper bound. Hence, we achieve the exact value of γoiR(Pn□Pm) for n ≤ 3 and the upper bound of γoiR(Pn□Pm) for n ≥ 4.