On the computational complexity of upper total domination Original Research Article

Let G=(V,E) be an undirected graph. Upper total domination number Γt(G) is the maximum cardinality over all minimal total dominating sets of G, and upper fractional total domination number Γt(G) is the maximum weight over all minimal total dominating functions of G. In this paper we show that: (1) Γt(G) is an optimal value of some linear programming and is always a rational number; (2) when G is a tree, Γt(G)=Γt(G); (3) the recognition problems corresponding to the problems of computing Γt(G) and Γt(G) are both NP-complete.