# On Resolvability- and Domination-Related Parameters of Complete Multipartite Graphs
## 3 Resolvability-Related Parameters
### Metric Dimension  
This section computes the metric dimension of complete multipartite graphs. Theorem 2: _Let \(K_{t_{1},t_{2},\ldots,t_{r}}\) be the complete \(r\)-partite graph with \(1\leq t_{1}\leq t_{2}\leq\ldots\leq t_{r}\) and \(\sum\limits_{i=1}^{r}t_{i}=n\). Then:_  
\[\beta(K_{t_{1},t_{2},\ldots,t_{r}})=\sum\limits_{i=1}^{r}t_{i}-r=n-r. \tag{2}\]  
Proof: First, we show the following two claims. Claim 1: _If \(r=2\), then \(\beta(K_{t_{1},t_{2}})=t_{1}+t_{2}-2\)._  
Proof of Claim 1: Assume \(T_{1}\) and \(T_{2}\) are partite sets of \(K_{t_{1},t_{2}}\), having \(|\ T_{1}\ |=t_{1}\) and \(|\ T_{2}\ |=t_{2}\). For any \(y\in T_{1}\) and \(z\in T_{2}\), we assume \(S=T_{1}\cup T_{2}\setminus\{y,z\}\). Note that \(S\) is a resolvingset of \(K_{t_{1},t_{2}}\), since \(r_{S}(y)=(\underbrace{2,2,\ldots,2}_{t_{1}-1\text{ times}},\underbrace{1,1, \ldots,1}_{t_{2}-1\text{ times}})\) and \(r_{S}(z)=(\underbrace{1,1,\ldots,1}_{t_{1}-1\text{ times}},\underbrace{2,2, \ldots,2}_{t_{2}-1\text{ times}})\). Since \(r_{S}(y)\
eq r_{S}(z)\), therefore, \(S\) is a resolving set. This implies that \(\beta\leq|\ S|=t_{1}+t_{2}-2\). On the other hand, let \(x\in S\) such that \(x\
otin\{y,z\}\). Let \(S^{\prime}=T_{1}\cup T_{2}\setminus\{x,y,z\}\). Assume, without loss of generality, that \(x\in T_{2}\). Then \(r_{S^{\prime}}(z)=r_{S^{\prime}}(x)=(\underbrace{1,1,\ldots,1}_{t_{1}-1\text { times}},\underbrace{2,2,\ldots,2}_{t_{2}-2\text{ times}})\). Since \(x\) was arbitrary and \(S^{\prime}\) is not a resolving set, we obtain that \(x\) must belong to \(S^{\prime}\). This implies that there is no resolving set of cardinality \(t_{1}+t_{2}-3\) in \(K_{t_{1},t_{2}}\), and thus, we have \(\beta(K_{t_{1},t_{2}})\geq t_{1}+t_{2}-2\). This complete the proof. **Claim 2. **_If \(r=3\), then \(\beta(K_{t_{1},t_{2},t_{3}})=t_{1}+t_{2}+t_{3}-2\)._  
**Proof of Claim 2. ** Let \(T_{1},\ T_{2}\) and \(T_{3}\) be three partite sets such that \(|T_{1}|=t_{1}\) and \(|T_{2}|=t_{2}\) and \(|T_{3}|=t_{3}\). Assume that \(R=T_{1}\cup T_{2}\cup T_{3}\setminus\{x,y,z\}\), for arbitrary \(x\in T_{1}\), \(y\in T_{2}\) and \(z\in T_{3}\). Note that \(R\) is a resolving set as \(r_{R}(x)\
eq r_{R}(y)\
eq r_{R}(z)\), where \(r_{R}(x)=(\underbrace{2,\ldots,2}_{t_{1}-1\text{ times}},\underbrace{1,\ldots,1}_{t_{2}-1 \text{ times}},\underbrace{1,\ldots,1}_{t_{1}-1\text{ times}})\) and \(r_{R}(y)=(\underbrace{1,\ldots,1}_{t_{1}-1\text{ times}},\underbrace{2,\ldots,2}_{t_{1}-1 \text{ times}},\underbrace{1,\ldots,1}_{t_{1}-1\text{ times}})\). Thus, we have \(\beta\leq|R|=t_{1}+t_{2}+t_{3}-3\). For arbitrary vertex \(w\in R\) where \(w\
otin\{x,y,z\}\), let \(R^{\prime}=T_{1}\cup T_{2}\cup T_{3}\setminus\{w,x,y,z\}\). Without loss of generality, we assume that \(w\in T_{1}\), then \(r_{R^{\prime}}(x)=r_{R^{\prime}}(w)=(\underbrace{2,\ldots,2}_{t_{1}-2\text{ times}},\underbrace{1,\ldots,1}_{t_{3}-1\text{ times}})\). This shows that \(R^{\prime}\) is not a resolving set. Since \(w\) was arbitrary, we see that there is no resolving set of cardinality \(t_{1}+t_{2}+t_{3}-4\). This implies that \(\beta(K_{t_{1},t_{2},t_{3}})\geq t_{1}+t_{2}+t_{3}-3\). Combining both inequalities, we obtain the result. For general \(r\), we apply induction on \(r\). By Claims 3.1 and 3.1, the result is true for \(r=2\) and \(r=3\), respectively. For the induction step, assume that (2) holds for \(r=k\). Now, we show that this is true for \(r=k+1\). Let \(T_{i}\) (\(1\leq i\leq r\)) be the \(i^{\text{th}}\) partite set with \(|T_{i}|=t_{i}\). Since Equation (2) holds for \(r=k\), we obtain that:  
\[\beta(K_{t_{1},t_{2},\ldots,t_{k}})=\sum\limits_{i=1}^{k}t_{i}-k,\]  
and that there exists a minimum resolving set \(R\) with \(|\ R\models\sum\limits_{i=1}^{k}t_{i}-k\). Note that \(R\) must contain \(t_{i}-1\) vertices from \(T_{i}\) for every \(1\leq i\leq k\); otherwise, if \(R\) would contain two vertices from the same partite set, then they would have the same distance representations. Furthermore, this would contradict the fact that \(R\) is a resolving set.