# On Resolvability- and Domination-Related Parameters of Complete Multipartite Graphs
## 4 Domination-Related Parameters
### Locating-Dominating Number  
First, we give the following characterization. Figure 6: The complete multipartite graph \(K_{2,3,5}\) with a minimum dominating set (red vertices). **Theorem 7**. : _Let \(\Gamma\) be an \(n\)-vertex connected graph with \(n\geq 2\). Then, \(\Gamma=K_{n}\) if and only if \(\gamma_{l-d}(\Gamma)=n-1\)._  
Proof. : First, we assume that \(\gamma_{l-d}(\Gamma)=n-1\) and show that \(\Gamma\) is a complete graph. Since \(\gamma_{l-d}(\Gamma)=n-1\), it implies that there exists a locating-dominating set of cardinality \(n-1\). Let \(V(\Gamma)=\{x_{1},x_{2},\ldots,x_{n}\}\). Without loss of generality, we may assume that \(S=\{x_{1},x_{2},\ldots,x_{n-1}\}\). Then, we have that \(x_{n}\in V\setminus S\). We will show that \(S\bigcap N[x_{n}]=S\). On the contrary, we suppose that \(S\bigcap N[x_{n}]\
eq S\). This implies that \(N[x_{n}]\
eq S\) such that \(|N[x_{n}]|<n-1\). Then, it implies that there exists an \(x^{\prime}\in V(\Gamma)\) such that \(x^{\prime}\
eq x_{n}\) and \(x^{\prime}\
sim x_{n}\). In that case, \(S\setminus\{x\}\), where \(x\in\{x_{i}:1\leq i\leq n-1\}\) is a locating-dominating set of \(\Gamma\), as we have \(S\bigcap N[x_{n}]\
eq S\bigcap N[x]\), since \(S\bigcap N[x_{n}]=S\setminus\{x\}\) and \(S\bigcap N[x]=S\). This contradicts the minimality of \(S\). Therefore, \(S\bigcap N[x_{n}]=S\), which implies that \(x_{n}\) is adjacent to all the \(x_{i}\), where \(1\leq i\leq n-1\). Since \(x_{n}\) was an arbitrary choice, we obtain that \(\Gamma=K_{n}\). For necessity, we assume that \(\Gamma=K_{n}\). Then, any subset of \(V(K_{n})\) on \(n-1\) vertices is a locating-dominating set of \(K_{n}\). This gives \(\gamma_{l-d}(K_{n})\leq n-1\). On the other hand, note that any subset of \(V(K_{n})\) on \(n-2\) elements can never be a binary locating-dominating set, as the two elements in \(S\setminus V(K_{n})\) would have the same intersections. This implies that \(\gamma_{l-d}(K_{n})\geq n-1\). This shows that \(\gamma_{l-d}(K_{n})=n-1\), which completes the proof. The next proposition computes the exact value of the locating-dominating number of the complete bipartite graphs. **Proposition 1**. : _Let \(K_{a,b}\) be the complete bipartite graph, where \(1\leq a\leq b\). Then \(\gamma_{l-d}(K_{a,b})=a+b-2\)._  
Proof. : Let \((A,B)\) be the bipartition of the vertex set of \(K_{a,b}\) such that \(|A|=a\) and \(|B|=b\). Note that the induced subgraphs on \(A\) and \(B\) are the empty graphs \(\overline{K_{a}}\) and \(\overline{K_{b}}\), respectively. Let \(x\in A\) and \(y\in B\) be the arbitrary vertices in \(A\) and \(B\), respectively. Note that the set \(S=A\setminus\{x\}\bigcup B\setminus\{y\}\) is a binary locating-dominating set of \(K_{a,b}\) as for both vertices \(x\) and \(y\), the sets \(S\cap N[x]=B\setminus\{y\}\) and \(S\cap N[y]=A\setminus\{x\}\) are mutually disjoint. Since \(|S|=a+b-2\), we obtain that \(\gamma_{l-d}(K_{a,b})\leq a+b-2\). Next, we prove the lower bound \(\gamma_{l-d}(K_{a,b})\geq a+b-2\). We will prove this by showing that \(\gamma_{l-d}(K_{a,b})\) cannot be \(a+b-3\). On contrary, we suppose that \(\gamma_{l-d}(K_{a,b})=a+b-3\). This implies that there exists a locating-dominating set \(S\) of cardinality \(a+b-3\). Let \(x,\ y\), and \(z\) be the three vertices in \(V\setminus S\). We distinguish the following possible cases for the vertices \(x,y\) and \(z\):  
**Case 1:** All the three vertices, \(x,\ y\), and \(z\), belong to one partite set. Without loss of generality, we may assume that \(x,\ y\), and \(z\), belong to \(A\). Note that \(S\cap N[x]=S\cap N[y]=S\cap N[z]=B\), which causes a contradiction to the fact any two such intersections must be disjointed. This suggests the following case:  
**Case 2:** Either \(x,\ y,\) or \(z\) belongs to a partite set different from the other two vertices. Without loss of generality, we may assume that \(x\in A\) and \(y,z\in B\). Then, \(S\cap N[y]=S\cap N[z]=A\), which again causes a contradiction that \(S\) preserves to be a locating-dominating set.