Proper Total Domination in Trees

A vertex u in a graph G totally dominates a vertex v if u is adjacent to v. A set S of vertices in a graph G is a total dominating set of G if every vertex of G is totally dominated by at least one vertex of S. For a total dominating set S of a graph G and a vertex v of G, let σS(v) denote the number of vertices in S that totally dominate v. A total dominating set S in a graph G is a proper total dominating set if σS(u)≠σS(v) for every two adjacent vertices u and v of G. While proper total dominating sets in trees have been previously studied, the primary goal here is to extend this study to classes of trees with a symmetric structure or that possess subtrees with a symmetric structure. Those trees belonging to several of the most-studied classes of trees that possess a proper total dominating set are determined. Graphical structures of proper total dominating sets in these trees are investigated. The minimum cardinality of a proper total dominating set in a graph G is the proper total domination number of G. Characterizations are obtained for all trees T with a small proper total domination number. Other results and problems are also presented on proper total dominating sets in trees in general.