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 su...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∈V)f(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 P_(n)□P_(m).With the help of computer,we find some recursive OIRDFs and then we present an upper bound ofγoiR(P_(n)□P_(m)).Furthermore,we prove the lower bound ofγoiR(P_(n)□P_(m))(n≤3)is equal to the upper bound.Hence,we achieve the exact value ofγoiR(P_(n)□P_(m))for n≤3 and the upper bound ofγoiR(P_(n)□P_(m))for n≥4.展开更多
文摘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∈V)f(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 P_(n)□P_(m).With the help of computer,we find some recursive OIRDFs and then we present an upper bound ofγoiR(P_(n)□P_(m)).Furthermore,we prove the lower bound ofγoiR(P_(n)□P_(m))(n≤3)is equal to the upper bound.Hence,we achieve the exact value ofγoiR(P_(n)□P_(m))for n≤3 and the upper bound ofγoiR(P_(n)□P_(m))for n≥4.
