Total domination and the Caccetta-H?ggkvist conjecture

详细信息    查看全文

• 作者：Patrick St-Louis ; Bernard Gendron ; Alain Hertz
• 关键词：Dominating sets ; Caccetta&ndash ; Hä ; ggkvist conjecture ; Smallest circuit
• 刊名：Discrete Optimization
• 出版年：2012
• 出版时间：November, 2012
• 年：2012
• 卷：9
• 期：4
• 页码：236-240
• 全文大小：282 K

文摘

A total dominating set in a digraph is a subset of its vertices such that every vertex of has an immediate successor in . The total domination number of 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 , where is the number of vertices of the smallest directed cycle contained in . We prove that these new conjectures are equivalent to the Caccetta-H?ggkvist conjecture which asserts that in every digraph on vertices with minimum outdegree at least .