### G-2009-78

# Total Domination and the Caccetta-Häggkvist Conjecture

## Patrick St-Louis, Bernard Gendron, and Alain Hertz

A total dominating set in a digraph *G* is a subset *W* of its vertices such that every vertex of *G* has an immediate successor in *W*. The total domination number of *G* is the size of the smallest total dominating set. We
consider several lower bounds on the total domination number and conjecture that these bounds are strictly larger than *g(G) - 1*, where *g(G)* is the number of vertices of the smallest directed cycle contained in *G*. We prove that
these new conjectures are equivalent to the Caccetta-Häggkvist conjecture which asserts that *g(G) - 1 < n/r* in every digraph on *n* vertices with minimum outdegree at least *r > 0*.

Published **December 2009**
,
12 pages