Dominating Sets of Random 2-in 2-out Directed Graphs

Abstract

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$.