Research On Roman {2}-domination Number Of Cartesian Product Of Paths

The domination theory of graphs originates from the practical problems in operation and optimization and it is an important research direction of graph theory.With the development of network and big data,graphs we are faced with are large and complex.The Cartesian product graph(product graph)is an important class of graphs with large scale and complex structure.To study the domination number of product graphs has theorical meaning and practical value.Roman {2}-domination(also called Italian domination or weak 2 domination)is a new kind of domination.It can be described as a defense problem.In old Roman Empire(graph G),every city(vertex)should be settled at most two troops and the cities with troops are safe.If a city having no troops is adjacent to at least two cities with one troop or one city with two troops,then the city is safe.If all cities in the R.oman Empire are safe,then such assignment is a Roman {2}-dominating function.In the case of ensuring that all cities are safe,the minimum number of troops is the Roman {2}-domination numer of G.In this paper,we study the Roman {2}-domination number of the Cartesian product of paths.To determine the Roman {2}-domination number is NP-hard.We develop some effective branch and bound conditions according to the characteristics of Pn□Pm.Based on them,we design some algorithms to construct recursive Roman {2}-dominating functions.Upon these functions,we get the upper bounds on the Roman {2}-domination number of Pn□Pm.Then we prove the lower bounds of the Roman {2}-domination number of Pn□P2 and Pn□P3 are equal to their upper bounds.Thus,we obtain the exact values of the Roman{2}-domination number of Pn□P2 and Pn□P3.And we present bounds on the Roman{2}-domination number of Pn□P2(n,m≥4).