\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Stephen Howe}
%
%
\medskip
\noindent
%
%
{\bf Dominating Sets of Random 2-in 2-out Directed Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
We analyse an algorithm for finding small dominating sets of $2$-in
$2$-out directed graphs using a deprioritised algorithm and
differential equations. This deprioritised approach determines an
a.a.s.\ upper bound of $0.39856n$ on the size of the smallest
dominating set of a random $2$-in $2$-out digraph on $n$
vertices. Direct expectation arguments determine a corresponding lower
bound of $0.3495n$.
\bye