## 2 Preliminaries  
Give an undirected connected graph \(G(V,E)\), where \(V=\{v_{1},v_{2},\,\ldots,\,v_{n}\}\) denotes the vertex set, and \(E=\{e_{1},e_{2},\,\ldots,\,e_{m}\}\) denotes the edge set. \(N(u)\) represents the opened neighbor set of vertex \(u\), denoted by \(N(u)=\{v\in V\,|\,\{v,u\}\in E\}\). \(\textit{deg}(u)=\,\mathbb{I}\,N(u)\,|\) denotes the degree of vertex \(u\). \(N[u]\) represents the closed neighbor set of vertex \(u\), denoted as \(N[u]=N(u)\cup[u]\). Similarly, for a vertex subset \(S\), \(N(S)=\bigcup\limits_{v\in S}N(v)\setminus S\), \(N[S]=N(S)\cup S\). The shortest distance between two vertices \(v\) and \(u\) in the graph is denoted as \(\textit{dist}(v,u)\). The \(i\)_-dist_ neighbor set of vertex \(v\) denotes \(N_{i}(u)=\{v\,\mathbb{I}\,1\leq\textit{dist}(v,\,u)\leq i\}\), and \(N_{i}[u]=N_{i}(u)\cup[u]\). The \(\textit{age}(v)\) value of vertex \(v\) is equal to the current iteration number when the state of vertex \(v\) changes (from dominated to undominated or from undominated to dominated). If vertex \(v\) is in the candidate solution, we say that vertex \(v\) dominates its neighbor set and itself. Here are some important definitions.  
Definition 1: (dominating set, DS). In an undirected graph \(G(V,E)\), a dominating set is a subset \(S\) of \(V\) such that each vertex in \(V\) is either in \(S\) or adjacent to at least one vertex in \(S\)[15].  
Definition 2: (connected dominating set, CDS). Given an undirected connected graph \(G(V,E)\), a subset \(D\) is a connected dominating set if every pair of vertices in \(D\) is connected by a path where all vertices on the path are also in \(D\)[6].  
We employed two scoring functions, namely _Dscore_ and _Mscore_[16], to guide the local search process. For a vertex \(v\), \(\textit{Dscore}(v)\) represents the number of vertices that change their status from non-dominated to dominated or vice versa among the neighbors of vertex \(v\) when vertex \(v\) is either added to or removed from the current candidate solution, as shown by Equation (1).  
\[\textit{Dscore}(v)=\begin{cases}|N[D\setminus\{v\}]|-|N[D]|,\text{ if }v\in D \\ |N[D\cup\{v\}]|\setminus N[D]|,\text{ if }v\
otin D\end{cases} \tag{1}\]  
where \(N[D]\) comprises the vertices within the current candidate solution \(D\) and their neighboring vertices; thus, \(N[D]\) can also be understood as the set of vertices dominated by the current candidate solution \(D\). Similarly, \(N[D\cup\{v\}]\) is the set of vertices dominated by the current candidate solution \(D\) after adding vertex \(v\). \(|N[D\setminus\{v\}]|\,|\) denotes the number of vertices dominated by the set \(D\setminus\{v\}\). According to Equation (1), \(\textit{Dscore}(v)\) is non-positive when vertex \(v\) is added to the candidate solution, and \(\textit{Dscore}(v)\) is non-negative when vertex \(v\) is removed from the candidate solution.  
For vertex \(v\), \(\textit{Mscore}(v)\) signifies the number of neighboring vertices of \(v\) that are present in the candidate solution, as expressed by Equation (2).  
\[\textit{Mscore}(v)=|N(v)\cap D| \tag{2}\]According to Formula (2), a vertex with a high _Mscore_ means that it is surrounded by many neighbors that have been selected for the dominating set, and removing such a vertex may be more likely to cause the dominating set to lose connectivity or reduce coverage.