## 1 Introduction
15:\(V\gets V\cup\{D^{\prime}\}\); \(E\leftarrow E\cup\{(D,D^{\prime})\}\). 16:\(\mathrm{parents}(D^{\prime})\leftarrow\{(D,x)\}\); \(\mathrm{children}(D^{\prime})\leftarrow\emptyset\); \(i(D^{\prime})\gets i(x)\). 17:\(\mathrm{children}(D)\leftarrow\mathrm{children}(D)\cup\{(D^{\prime},x)\}\). 18:for all\((A,a)\in\mathrm{parents}(D)\)do
19:for all\((B,b)\in\mathrm{children}(A)\)do
20:if\(b=x\)then
21:\(E\leftarrow E\cup\{(D^{\prime},B)\}\). 22:\(\mathrm{children}(B)\leftarrow\mathrm{children}(B)\cup\{(D^{\prime},a)\}\). 23:\(\mathrm{parents}(D^{\prime})\leftarrow\mathrm{parents}(D^{\prime})\cup\{(B,a)\}\). 24:endif
25:endfor
26:endfor
27:endfor
28:endfor
29:endprocedure
```  
**Algorithm 2** Let \(T\) be a tree rooted at a vertex \(c\) and let \(S\) be the highest \(\gamma\)-set of \(T\). For every \(\gamma\)-set \(D\
eq S\) found by GAMMATREE\((T,c,S)\),  
\[i(D)=\max_{v\in D-S}i(v).\]  
Suppose \(D^{\prime}\) is the first \(\gamma\)-set of \(T\) found by GAMMATREE\((T,c,S)\) such that \(i(D^{\prime})\) is not the largest index of the vertices of \(D^{\prime}\) not appearing in \(S\). By definition of \(i(D^{\prime})\), there exists a \(\gamma\)-set \(D\) and vertices \(v,x\) such that \(i(D^{\prime})=i(x)\), \(D^{\prime}=(D-\{v\})\cup\{x\}\) and \(i(x)>i(D)\). Suppose first that \(y\) is a vertex in \(D^{\prime}-S\) such that \(i(y)>i(D^{\prime})\). By choice of \(D^{\prime}\), we have that \(i(D)=\max_{u\in D-S}i(u)\) and since \(y\in D\), \(i(D)\geq i(y)\). Hence, \(i(D^{\prime})=i(x)>i(D)\geq i(y)>i(D^{\prime})\)which is a contradiction. Therefore, \(i(y)\leq i(x)\) for all \(y\in D^{\prime}-S\) and if \(x\in D^{\prime}-S\) so we assume \(x\in D^{\prime}\cap S\). Hence any vertex in \(D^{\prime}\) with an index at least \(i(x)\) must also be in \(S\). In particular, \(x\), and every descendant of \(x\) in \(D^{\prime}\) must also be in \(S\). By Lemma 1, \(x\), and every descendant of \(x\) in \(S\) has a child \(S\)-private neighbour which is also a child \(D^{\prime}\)-private neighbour. Let \(w\) be a child \(S\)-private neighbour of \(x\) which is also a child \(D^{\prime}\)-private neighbour of \(x\). Clearly \(w\
otin S\). As \(D\) is dominating and \(D=(D^{\prime}-\{x\})\cup\{v\}\), it must be the case that \(v=w\). Hence \(i(D)=\max_{u\in D-S}\geq i(w)>i(x)\), which is a contradiction as \(i(x)>i(D)\). The result follows. Let \(T\) be a tree rooted at a vertex \(c\) and let \(S\) be the highest \(\gamma\)-set of \(T\). Every \(\gamma\)-set \(D\
eq S\) of \(T\) is obtained by GAMMATREE(\(T,c,S\)). Proof. : Assume there is a \(\gamma\)-set of \(T\) which is not obtained by GAMMATREE(\(T,c,S\)). For a \(\gamma\)-set \(D=\{v_{1}\), \(v_{2}\), \(\ldots\), \(v_{\gamma(T)}\}\) of \(T\), we define \(I(D)=\{i(v_{1})\), \(i(v_{2})\), \(\ldots\), \(i(v_{\gamma(T)})\}\), where \(i(v_{1})<i(v_{2})<\cdots<i(v_{\gamma(T)})\). Let \(D^{\prime}\) be the \(\gamma\)-set not obtained by GAMMATREE(\(T,c,S\)) for which \(I(D^{\prime})\) is lexicographically smallest. Let \(x\) be so that \(i(x)=i(D^{\prime})\). Then every descendant of \(x\) in \(D^{\prime}\) has a higher index and hence is also in \(S\). It follows from Lemma 1, each descendant of \(x\) in \(D^{\prime}\) has a child \(D^{\prime}\)-private neighbour. If \(x\) also has a child \(D^{\prime}\)-private neighbour, then every higher \(\gamma\)-set of \(T\) must contain \(x\), contradicting that \(x\
otin S\). Hence, no child of \(x\) is a \(D^{\prime}\)-private neighbour. Therefore, if \(v\) is the parent of \(x\), then the set \(D=D^{\prime}-\{x\}\cup\{v\}\) is a \(\gamma\)-set of \(T\). Since \(I(D)\) is lexicographically smaller than \(I(D^{\prime})\), \(D\) is found by GAMMATREE(\(T,c,S\)). Clearly each vertex in \(D-S\subseteq(D^{\prime}-S)\cup\{v\}\) has a smaller index than \(x\), so \(i(x)>i(D)\). Further, as \(D\) and \(D^{\prime}\) are both \(\gamma\)-sets of \(T\), \(pn(v,D)\subseteq\{v,x\}\), so for \(v\in D\), \(x\in\) Swap. Hence, \(D^{\prime}\) is found by GAMMATREE(\(T,c,S\)), which is a contradiction proving the theorem.