|
Roman problem is a location problem which approached by the Emperor Constantine in the 4th century. In the 3rd century, when Rome dominated Europe, it was able to deploy 50 legions throughout the empire, securing even the furthermost areas. By the following century the empire had lost much of its muscle, however, and Rome’s forces had diminished to just 25 legions. So, how to defend the Roman Empire from multiple attacks by stationing as few legions as possible will be the most important problem.ReVelle suggested Roman domination in 1997, a few years earlier. Stewart and ReVelle give the definition of Roman domination with graph theory in 1999. For a graph G = （V,E）,let f: V→{0,1,2}, and let （V0,V1,V2） be the ordered partition of V induced by f, whereVi={v∈V|f（v） = i} and |Vi| = ni, for i = 0,1,2. A function f = （V0,V1,V2） is a Roman dominatingfunction （RDF） if V2 dominates V0, i.e. V2 （?） V0. And the weight of /is f（V）=∑v∈V f（v） = 2n2 + n1. The minimum weight of an RDF of G is called the Romandomination number of G, denoted byγR （G）, and we say that a function f= （V0, V1, V2） is aγR- function if it is an RDF and f（V） =γR（G）.In this paper, with the algorithm of calculating the roman domination number of graphs, we study the roman domination number of generalized Petersen graphs P（n, k） and circulant graphs C（n; {1, k}） and then get the following conclusions.For generalized Petersen graphs P（n,k） and circulant graphs C（n;{1,k}）, the upper bounds of their roman domination numbers are given.
|