Skip navigation
Skip navigation

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

Howe, Stephen


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.

CollectionsANU Research Publications
Date published: 2008
Type: Journal article
Source: Electronic Journal of Combinatorics


File Description SizeFormat Image
01_Howe_Dominating_sets_of_random_2-in_2008.pdf188.74 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator