COCOA Talk: 2000-02

Speaker: Paul Dreyer

For a graph $G = (V,E)$, a {\it dominating set} is a subset of the
vertices such that for all $v \in V$ either $v \in D$ or there exists
an edge between $v$ and some member of $D$.  The {\it domination   
number} of $G$ is the size of the smallest dominating set. 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 {\it Scientific American} entitled ``Defend the Roman
Empire!''.\\

A {\it Roman dominating function} on a graph $G = (V,E)$ is a function
$f: V \rightarrow \{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 {\it weight} of a Roman dominating
function is the value $f(V)$ = \(\sum_{u \in V} f(u)\).  The minimum
weight of a Roman dominating function is called the {\it 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.

DIMACS Home Page