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

Stephen Howe*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Article numberR29
JournalElectronic Journal of Combinatorics
Volume15
Issue number1 R
DOIs
Publication statusPublished - 11 Feb 2008
Externally publishedYes

Fingerprint

Dive into the research topics of 'Dominating sets of random 2-in 2-out directed graphs'. Together they form a unique fingerprint.

Cite this