Vertices contained in all or in no minimum total dominating set of a tree (Q1861240)

In an undirected simple graph \(G=(V,E)\), a total dominating set (TDS) is a subset \(S\) of \(V\) such that every vertex of \(V\) is adjacent to some vertex of \(S\). The total domination number \(\gamma_t(G)\) is the minimum cardinality of a TDS; a \(\gamma_t(G)\)-set is a TDS of cardinality \(\gamma_t(G)\). \({\mathcal A}_t(G)\) and \({\mathcal N}_t(G)\) are respectively the subsets of \(V\) whose members are in every \(\gamma_t(G)\)-set, and in no \(\gamma_t(G)\)-set. For any tree \(T=(V,E)\), \(L(T)\) and \(S(T)\) respectively denote the sets of leaves (vertices of degree 1) and support vertices (vertices adjacent to a leaf); if \(T\) is ``rooted'', the set of descendants of a vertex \(v\) is denoted by \(D(v)\); \(T_v\) is the subtree rooted at \(v\) which is induced by \(D(v)\cup\{v\}\); \(L(v)=D(v)\cap L(T)\). Denoting the distance between vertices \(u\), \(v\) by \(d(u,v)\), the authors define, for any integer \(j\), \(L_T^j(v)=\{u\in L(v):d(u,v)\equiv j\pmod 4\}\). A procedure called pruning is described, under which a rooted tree \(T_v\), in which \(v\notin S(T)\), is transformed into a unique tree \({\overline{T}}_v\); \(L^j_{{\overline{T}}_v}(v)\) is abbreviated to \(\overline{L}^j(v)\). Theorem 1. Let \(T\) be a tree rooted at \(v\), wherein all vertices \(u\in V(T)-\{v\}\) have degree not exceeding 2. Then \({\mathcal A}_t(T)=S(T)\cup\{v:|L^1(v)\cup L^2(v)|\geq 2\}\), and \({\mathcal N}_t(T)=\{v:L^1(v)\cup L^2(v)=\emptyset\}\). Theorem 2. Let \(T\) be a tree rooted at \(v\). Then \({\mathcal A}_t(T)=S(T)\cup\{v:|\overline{L}^1(v)\cup \overline{L}^2(v)|\geq 2\}\), and \({\mathcal N}_t(T)=\{v:\overline{L}^1(v)\cup\overline{L}^2(v)=\emptyset\}\).