# zbMATH — the first resource for mathematics

Vertices contained in all or in no minimum total dominating set of a tree. (English) Zbl 1013.05054
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\}$$.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C05 Trees
##### Keywords:
total domination; total domination number; tree
Full Text: