For a graph G = (V,E), a dominating set is a subset of the vertices such that for all v in V either v is in D$ or there exists an edge between v and some member of D. The domination number of G is the size of the smallest dominating set. My thesis research is on applications and variations of dominating sets in graphs, and this talk will address a variant of domination that arose in research by Rosing and ReVelle into a problem of army placement. Their work is discussed in an article by Ian Stewart in the December, 1999 issue of Scientific American entitled "Defend the Roman Empire!".

A Roman dominating function on a graph G = (V,E) is a function f: V --> {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the sum of the values of the f(v) over all of the vertices and is denoted f(V). The minimum weight of a Roman dominating function is the Roman domination number of a graph G. In this talk, I will discuss a series of results about the Roman domination number and relate it to some other problems in facility location.