Howe, Stephen

Dominating sets of random 2-in 2-out directed graphs

Electron. J. Comb. 15(1), Research Paper R29, 21 p. (2008)


Summary: 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.

Mathematics Subject Classification

05C80, 05C69, 05C20