## DCI'00

**Paul Dreyern**
*Rutgers University*

*Dominating the Roman Empire*

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.