On the Algorithmic Complexity of Total Domination

Abstract

A set of vertices D is a dominating set for a graph $G = (V,E)$ if every vertex not in D is adjacent to a vertex in D. A set of vertices is a total dominating set if every vertex in V is adjacent to a vertex in D. Cockayne, Goodman and Hedetniemi presented a linear time algorithm to determine minimum dominating sets for trees. Booth and Johnson established the NP-completeness of the problem for undirected path graphs. This paper presents a linear time algorithm to determine minimum total dominating sets of a tree and shows that for undirected path graphs the problem remains NP-complete.