Groupe d’études et de recherche en analyse des décisions

Total Domination and the Caccetta-Häggkvist Conjecture

Patrick St-Louis, Bernard Gendron et 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.

, 12 pages