Total domination in block graphs (Q1124531)

A set of vertices D is a total dominating set for a graph G if every vertex of G is adjacent with at least one vertex in D. Although the problem of determining the minimum cardinality of a total dominating set for an arbitrary graph is NP-complete, polynomial time algorithm are known for certain classes of graphs (e.g. trees, interval graphs). The paper contains an \(O(| V| +| E|)\) time algorithm which solves this problem for block graphs. In fact, the algorithm presented here deals with a more general problem which, for particular instances, gives solutions for both domination and total domination problems.