Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141720 | Discrete Optimization | 2012 | 5 Pages |
Abstract
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)â10.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Patrick St-Louis, Bernard Gendron, Alain Hertz,