Proof Without loss of generality, assume that W can distinguish $V{\kern-1.5pt}={\kern-1pt}\{v_1,v_2,\ldots ,v_x\}$ . Let $W_1$ be the intersection of W and V, and p the cardinality of $W_1$ . We can assume $p\leq x-2$ , and then assume $V\backslash W_1=\{v_{i_1},\ldots ,v_{i_{x-p}}\}$ , where $i_1<\cdots <i_{x-p}$ . It follows that $W\backslash W_1$ can distinguish $x-p-1$ pairs of vertices $(v_{i_1},v_{i_2}),\ldots ,(v_{i_{x-p-1}},v_{i_{x-p}})$ . Suppose $w_j\in W\backslash W_1$ can resolve $(v_{i_j},v_{i_{j+1}})$ for each such j, then it can resolve two consecutive vertices in the $v_{i_j}-v_{i_{j+1}}$ path of the outer cycle, say $v_{i_j^{'}}$ and $v_{i_j^{'}+1}$ . Since $r=t$ , and since the distance between $v_{i_1}$ and $v_{i_j^{'}}$ on the outer cycle is no more than $t-2$ , it follows from equation (1.1) that $d(v_{i_1},w_j)=d(v_{i_1+1},w_j)=\cdots =d(v_{i_j^{'}},w_j)$ , and thus none of the pairs $(v_{i_1},v_{i_2}),\ldots ,(v_{i_{j-1}},v_{i_{j}})$ can be resolved by $w_j$ . A similar argument shows that none of the pairs $(v_{i_{j+1}},v_{i_{j+2}}),\ldots ,(v_{i_{x-p-1}},v_{i_{x-p}})$ can be resolved by $w_j$ . Therefore, any vertex in $W\backslash W_1$ resolving one of the pairs $(v_{i_1},v_{i_2}),\ldots ,(v_{i_{x-p-1}},v_{i_{x-p}})$ cannot resolve the other, implying that $W\backslash W_1$ consists of at least $x-p-1$ vertices, and so $\sharp (W)\geq x-1$ .

Proof Let W be a resolving set of the graph $C_n(1,2,\ldots ,t)$ . Suppose on the contrary that $\sharp (W)=t$ . We can assume $v_0\in W$ .

Let us first show that $W\cap \{v_{i-tk},v_{i+tk}\}\neq \emptyset $ holds for each vertex $v_i\in W$ . Suppose on the contrary that there exists a vertex $v_j\in W$ with $W\cap \{v_{j-tk},v_{j+tk}\}=\emptyset $ , since the circulant graph $C_n(1,2,\ldots ,t)$ is vertex-transitive, and we may take $j=0$ . Let $p\geq 0$ be such that $v_{n-0},v_{n-1},\ldots ,v_{n-p}$ all belong to W while $v_{n-p-1}\notin W$ , and let $q\geq 0$ be such that $v_{0},v_{1},\ldots ,v_{q}$ all belong to W while $v_{q+1}\notin W$ . It is easy to see that $p+q\leq t-1$ . Set $W_1=\{v_{n-p},v_{n-p+1},\ldots ,v_{q}\}$ . Then there is a vertex $w\in W\backslash {W_1}$ that resolves $v_{n-p-1}$ and $v_{q+1}$ . If $p+q=t-1$ , then W consists of at least $t+1$ vertices, leading to the contradiction. Suppose now that $p+q\leq t-2$ . One can verify that there are two consecutive vertices $v_i$ and $v_{i+1}$ in the $v_{n-p-1}-v_{q+1}$ path of the outer cycle, which can be resolved by w. By symmetry, we can assume $n-t+1\leq i\leq n-1$ .

First, consider the case $n-t+1\leq i\leq n-2$ . Note that $\{v_{i+1},v_{i+2},\ldots ,v_n\}\subset W_1$ , and that $W\backslash (\{v_{i+1},v_{i+2},\ldots ,v_n\}\cup \{w\})$ can distinguish $\{v_{n-t},v_{n-t+1},\ldots ,v_{i}\}$ , which consists of $i+t+1-n$ vertices. It follows from Lemma 2.2 that $W\backslash (\{v_{i+1},v_{i+2},\ldots ,v_n\}\cup \{w\})$ has at least $i+t-n$ vertices, and therefore $\sharp (W)\geq t+1$ , a contradiction.

Next, consider the case where $i=n-1$ . Since $w\notin \{v_{n-1},v_0,v_{kt}\}$ , and since $r=t$ , it follows from equation (1.1) that vertices $v_{n-t},v_{n-t+1},\ldots ,v_{n-1}$ have equal distance to w. Hence, $W\backslash \{v_0,w\}$ can distinguish $\{v_{n-t},v_{n-t+1},\ldots ,v_{n-1}\}$ , and applying Lemma 2.2, $W\backslash \{v_0,w\}$ has at least $t-1$ vertices, and therefore W consists of at least $t+1$ vertices, which is a contradiction.

We have already verified that $W\cap \{v_{i-tk},v_{i+tk}\}\neq \emptyset $ holds for each vertex $v_i\in W$ . We now claim that $|W\cap \{v_{i-tk},v_{i+tk}\}|=1$ holds for each vertex $v_i\in W$ . Suppose on the contrary that there is a vertex $v_j\in W$ with $\{v_{j-tk},v_{j+tk}\}\subset W$ , and we may also take $j=0$ . Then $W\backslash \{v_0,v_{kt},v_{n-kt}\}$ can distinguish $\{v_{kt+1},v_{kt+2},\ldots ,v_{kt+t-1}\}$ , and applying Lemma 2.2, $W\backslash \{v_0,v_{kt},v_{n-kt}\}$ consists of at least $t-2$ vertices, and so $\sharp (W)\geq t+1$ , a contradiction.

In conclusion, for each vertex $w\in W$ , there exists exactly one vertex, say $w_1$ , in W such that $w_1$ has distance $kt$ from w on the outer cycle, and we say $\{w,w_1\}$ form a “pair” in W. It is easy to see that these “pairs” in W are pairwise disjoint. Hence, the cardinality of W is even, which contradicts the assumption that $\sharp (W)=t$ is odd.

Proof Suppose that $v_{i_1},\ldots ,v_{i_x}$ come from a clique of $x+1$ consecutive vertices, where $i_1<i_2<\cdots <i_x$ , and suppose that W can distinguish them.

We first deal with the case where $r\in \{t+1,t+2,\ldots ,2t+1\}$ . Let $V=\{v_{i_1},\ldots ,v_{i_x}\}$ , and let $W_1$ be the intersection of W and V, and p the cardinality of $W_1$ . We can assume $p\leq x-2$ , and then assume $V\backslash W_1=\{v_{j_1},\ldots ,v_{j_{x-p}}\}$ , where $j_1<\cdots <j_{x-p}$ . It follows that $W\backslash W_1$ can distinguish $x-p-1$ pairs of vertices $(v_{j_1},v_{j_2}),\ldots ,(v_{j_{x-p-1}},v_{j_{x-p}})$ .

We remark that since $t+1\leq r\leq 2t+1$ , if a vertex w can resolve two consecutive vertices $v_i$ and $v_{i+1}$ , and if $w\neq v_i,v_{i+1}$ , then it follows from equation (1.1) that

$$ \begin{align*}d(w,v_{i-t+1})=d(w,v_{i-t+2})=\cdots=d(w,v_{i}) \end{align*} $$

and

$$ \begin{align*}d(w,v_{i+1})=d(w,v_{i+2})=\cdots=d(w,v_{i+t}). \end{align*} $$

This remark shows that any vertex in $W\backslash W_1$ resolving one of the pairs of vertices $(v_{j_1},v_{j_2}),\ldots ,(v_{j_{x-p-1}},v_{j_{x-p}})$ cannot resolve the other, implying $W\backslash W_1$ consists of at least $x-p-1$ vertices, and therefore $\sharp (W)\geq x-1$ .

Let us turn to the case where $r=2$ . Let $V^{'}=\{v_{i_1}^{'},\ldots ,v_{i_x}^{'}\}$ , and let $W_2$ be the intersection of W and $V^{'}$ . Denote by q the cardinality of $W_2$ . We can assume that $p+q\leq x-2$ , and then assume $V\backslash (W_1\cup W_2^{'})=\{v_{j_1},\ldots ,v_{j_{s}}\}$ , where $j_1<\cdots <j_{s}$ and $s\geq x-p-q$ . It follows that $W\backslash (W_1\cup W_2)$ can distinguish $s-1$ pairs of vertices $(v_{j_1},v_{j_2}),\ldots ,(v_{j_{s-1}},v_{j_{s}})$ . Similarly, any vertex in $W\backslash (W_1\cup W_2)$ resolving one of these pairs cannot resolve the other, implying $W\backslash (W_1\cup W_2)$ consists of at least $s-1$ vertices, and therefore $\sharp (W)\geq x-1$ .

Proof It is sufficient to show that any resolving set W of the graph $C_n(1,2,\ldots ,t)$ has at least $t+1$ vertices. Without loss of generality, we assume $v_0\in W$ .

Let us first discuss the case where $r\in \{t+1,t+2,\ldots ,2t\}$ . Let $p\geq 0$ be such that $v_{n-0},v_{n-1},\ldots ,v_{n-p}$ all belong to W while $v_{n-p-1}\notin W$ , and let $q\geq 0$ be such that $v_{0},v_{1},\ldots ,v_{q}$ all belong to W while $v_{q+1}\notin W$ . We can assume $p+q\leq t-1$ . Set $W_1=\{v_{n-p},v_{n-p+1},\ldots ,v_{q}\}$ . Then there is a vertex $w\in W\backslash {W_1}$ that resolves $v_{n-p-1}$ and $v_{q+1}$ , and therefore there exist two consecutive vertices $v_i$ and $v_{i+1}$ in the $v_{n-p-1}-v_{q+1}$ path of the outer cycle which can be resolved by w. By symmetry, assume $0\leq i\leq q$ . Since $r\geq t+1$ , it follows from equation (1.1) that $v_{i+1},v_{i+2},\ldots ,v_t$ have equal distance to w. Hence, $W\backslash (W_1\cup \{w\})$ can distinguish $\{v_{q+1},\ldots ,v_{t-p}\}$ , which consists of $t-p-q$ consecutive vertices. Applying Lemma 2.4, $W\backslash (W_1\cup \{w\})$ has at least $t-p-q-1$ vertices, and thus W has at least $t+1$ vertices.

The proof for the case where $r=2$ is analogous to that for the preceding case. We first note that the definitions of p and q are changed, that is, let $p\geq 0$ be such that $v_{n-0},v_{n-1},\ldots ,v_{n-p}$ all belong to the union of W and $W^{'}$ while $v_{n-p-1}\notin W\cup W^{'}$ , and $q\geq 0$ such that $v_{0},v_{1},\ldots ,v_{q}$ all belong to the union of W and $W^{'}$ while $v_{q+1}\notin W\cup W^{'}$ . Set

$$ \begin{align*}W_2=\left(\{v_{n-p},v_{n-p+1},\ldots,v_{q}\}\cup\{v_{n-p}^{'},v_{n-p+1}^{'},\ldots,v_{q}^{'}\}\right)\cap W, \end{align*} $$

where $\sharp (W_2)\geq p+q+1$ . An entirely similar argument shows that there is a vertex $w\in W\backslash {W_2}$ that resolves $v_{n-p-1}$ and $v_{q+1}$ , and that $W\backslash (W_2\cup \{w\})$ has at least $t-p-q-1$ vertices, implying $\sharp (W)\geq t+1$ .

Proof It is sufficient to show that any resolving set W for the graph $C_n(1,2,\ldots ,t)$ has at least $t+2$ vertices. Without loss of generality, we assume $v_0\in W$ . The only vertices that can resolve $v_{dt}$ and $v_{dt+1}$ are

$$ \begin{align*}v_{n-t},v_{n-2t},\ldots,v_{n-dt}=v_{dt+1},v_{dt},v_{dt-t},\ldots,v_{t}. \end{align*} $$

By symmetry, we assume $v_{n-pt}\in W$ , where $p\in \{1,2,\ldots ,d\}$ . We shall consider two cases.

Case 1 ( $p\leq k$ ): The only vertices that can resolve $v_{dt+1}$ and $v_{dt+2}$ are

$$ \begin{align*}v_{n+1-t},v_{n+1-2t},\ldots,v_{n+1-dt}=v_{dt+2},v_{dt+1},v_{dt+1-t},\ldots,v_{t+1}. \end{align*} $$

If $v_{qt+1}\in W$ for some $q\in \{1,\ldots ,d\}$ , one can easily verify that $\{v_0,v_{qt+1},v_{n-pt}\}$ cannot distinguish any pair of vertices in $\{v_1,v_2,\ldots ,v_t\}$ . It follows from Lemma 2.4 that $W\backslash \{v_0,v_{qt+1},v_{n-pt}\}$ has at least $t-1$ vertices, which confirms the assertion. If $v_{n+1-qt}\in W$ for some $q\in \{1,\ldots ,d\}$ , it is easy to see that $\{v_0,v_{n+1-qt},v_{n-pt}\}$ cannot distinguish any pair of vertices in $\{v_{(d-q)t+1},v_{(d-q)t+2},\ldots ,v_{(d-q+1)t}\}$ , and according to Lemma 2.4, $W\backslash \{v_0,v_{n+1-qt},v_{n-pt}\}$ has at least $t-1$ vertices, and therefore W has at least $t+2$ vertices.

Case 2 ( $p=d$ ): The only vertices that can resolve $v_{kt+1}$ and $v_{kt+2}$ are

$$ \begin{align*}v_{n+1-2t},\ldots,v_{n+1-dt},v_{n+1-dt-t}=v_{kt+2},v_{kt+1},v_{kt+1-t},\ldots,v_{1}. \end{align*} $$

If $v_{qt+1}\in W$ for some $q\in \{1,2,\ldots ,k\}$ , one can verify that $\{v_0,v_{qt+1},v_{n-dt}\}$ cannot distinguish any pair of vertices in $\{v_1,v_2,\ldots ,v_t\}$ . If $v_{n+1-qt}\in W$ for some $q\in \{2,3,\ldots ,d\}$ , one can verify that $\{v_0,v_{n+1-qt},v_{n-dt}\}$ cannot distinguish any pair of vertices in $\{v_{(d-q)t+1},v_{(d-q)t+2},\ldots ,v_{(d-q+1)t}\}$ . If $v_{kt+2}\in W$ , then it is easy to see that $\{v_0,v_{kt+2},v_{n-dt}\}$ cannot distinguish any pair of vertices in $\{v_{n-(t-1)},\ldots ,v_{n-2},v_{n-1},v_1\}$ , which consists of t vertices coming from a clique of $t+1$ consecutive vertices. If $v_{1}\in W$ , then $\{v_0,v_{1},v_{n-dt}\}$ cannot distinguish any pair of vertices in $\{v_{dt},v_{dt+2},v_{dt+3},\ldots ,v_{dt+t}\}$ . In both cases, it follows quickly from Lemma 2.4 that W has at least $(t-1)+3=t+2$ vertices. The proof is complete.

Proof Let

$$ \begin{align*}W_1=\{v_0,v_2,\ldots,v_{t-1}\}\quad\text{and}\quad W_2=\{v_{kt},v_{kt+2},v_{kt+4},\ldots,v_{kt+t+p-3}\}, \end{align*} $$

where $\sharp (W_1)=\frac {t+1}{2}$ and $\sharp (W_2)=\frac {t+p-1}{2}$ . Let us show that $W=W_1\cup W_2$ is a resolving set of the graph $C_n(1,2,\ldots ,t)$ . Divide the vertex set of $C_n(1,2,\ldots ,t)$ into four disjoint sets:

$$ \begin{align*} &V_1=\{v_0,v_1,\ldots,v_t\}, V_2=\{v_{t+1},v_{t+2},\ldots,v_{kt-1},v_{kt}\},\\ &V_3=\{v_{kt+1},v_{kt+2},\ldots,v_{kt+t+p-2},v_{kt+t+p-1}\},V_4=\{v_{kt+t+p},v_{kt+t+p+1},\ldots,v_{n-2},v_{n-1}\}. \end{align*} $$

We claim that any pair of distinct vertices $u\in V_{r_1}$ and $v\in V_{r_2}$ have different metric representations with respect to W. We need only consider the following six cases, since in other cases, it is easy to check that $v_0$ can resolve u and v.

Case 1 ( $r_1=r_2=1$ ): It suffices to prove that no two vertices in $V_1\backslash W_1=\{v_j:j=1,3,\ldots ,t\}$ have the same metric representation with respect to $W_{21}:=\{v_{kt+2},v_{kt+4},\ldots ,v_{kt+t-1}\}$ ; $W_{21}$ is obviously a subset of $W_2$ . We observe that for $j=1,3,\ldots ,t$ , $r(v_j|W_{21})=(k,\ldots ,k,k+1,\ldots ,k+1)$ , of which the first $\frac {j-1}{2}$ entries are equal to k, and the other $\frac {t-j}{2}$ entries are equal to $k+1$ , the desired result follows.

Case 2 ( $r_1=r_2=2$ ): For $x=1,\ldots ,k-1$ and $j=1,2,\ldots ,t$ , the metric representation of $v_{tx+j}\in V_2$ with respect to $W_1$ is

$$ \begin{align*}r(v_{tx+j}|W_1)=(\underbrace{x+1,\ldots,x+1}_{\left\lceil\frac{j}{2}\right\rceil},\underbrace{x,\ldots,x}_{\frac{t+1}{2}-\left\lceil\frac{j}{2}\right\rceil}). \end{align*} $$

Hence, the only vertices in $V_2$ with the same metric representations with respect to $W_1$ are the pairs $(v_{tx+j-1},v_{tx+j})$ , where $j=2,4,\ldots ,t-1$ and $x=1,2,\ldots ,k-1$ . Since $v_{kt+j}$ belongs to $W_2$ for each $j\in \{2,4,\ldots ,t-1\}$ , and since

$$ \begin{align*}d(v_{kt+j},v_{tx+j-1})=k-x+1\quad\text{and}\quad d(v_{kt+j},v_{tx+j})=k-x, \end{align*} $$

it follows that $W_2$ can distinguish all these pairs.

Case 3 ( $r_1=r_2=3$ ): Note that

$$ \begin{align*} &r(v_{kt+j}|W_1)=(\overbrace{k+1,\ldots,k+1}^{\left\lceil\frac{j}{2}\right\rceil},\overbrace{k,\ldots,k}^{\frac{t+1}{2}-\left\lceil\frac{j}{2}\right\rceil})\quad\text{for}\,\, j=1,2,\ldots,t-1, \\ &r(v_{kt+j}|W_1)=(k+1,\ldots,k+1)\quad\text{for}\,\,j=t,t+1,\ldots,t+p-1. \end{align*} $$

Write $u=v_{kt+j_1}$ and $v=v_{kt+j_2}$ . We need only consider the following two subcases, since in other cases, $v_{t-1}\in W_1$ can already resolve u and v.

Case 3.1 ( $j_1<t$ , $j_2<t$ ): In this case, the only vertices with the same metric representations with respect to $W_1$ are the pairs $(v_{kt+j-1},v_{kt+j})$ , where $j=2,4,\ldots ,t-1$ . Since $W_2$ contains $v_{kt+j}$ for each $j\in \{2,4,\ldots ,t-1\}$ , it follows that $W_2$ can distinguish these pairs.

Case 3.2 ( $j_1\geq t$ , $j_2\geq t$ ): Recalling the construction of $W_2$ , we need only show that no two vertices in $\{v_{kt+t+j}:j=0,2,\ldots ,p-2\}\cup \{v_{kt+t+p-1}\}$ have the same metric representation with respect to $W_{22}:=\{v_{kt},v_{kt+2},\ldots ,v_{kt+p-2}\}$ ; $W_{22}$ is obviously a subset of $W_2$ . We observe that $r(v_{kt+t+j}|W_{22})=(2,\ldots ,2,1,\ldots ,1)$ , $j=0,2,\ldots ,p-2$ , of which the first $\frac {j}{2}$ entries are equal to $2$ and the other $\frac {p-j}{2}$ entries are equal to $1$ , and that all the distances from $v_{kt+t+p-1}$ to the vertices in $W_{22}$ are $2$ ; the desired result follows.

Case 4 ( $r_1=r_2=4$ ): It is not difficult to see that for $x=1,2,\ldots ,k$ and $j=0,1,\ldots ,t-1$ , the metric representation of $v_{n-tx+j}\in V_4$ with respect to $W_1$ is

$$ \begin{align*}r(v_{n-tx+j}|W_1)=(\underbrace{x,\ldots,x}_{\left\lfloor\frac{j}{2}\right\rfloor+1},\underbrace{x+1,\ldots,x+1}_{\frac{t-1}{2}-\left\lfloor\frac{j}{2}\right\rfloor}). \end{align*} $$

Thus, the only vertices in $V_4$ with the same metric representations with respect to $W_1$ are the pairs $(v_{n-tx+j},v_{n-tx+j+1})$ , where $j=0,2,\ldots ,t-3$ and $x=1,2,\ldots ,k$ . Since $v_{n-kt-t+j}$ belongs to $W_2$ for each $j\in \{0,2,\ldots ,t-3\}$ , and since

$$ \begin{align*}d(v_{n-kt-t+j},v_{n-tx+j})=k+1-x\quad\text{and}\quad d(v_{n-kt-t+j},v_{n-tx+j+1})=k+2-x, \end{align*} $$

it follows that $W_2$ can distinguish these pairs.

Case 5 ( $r_1=1$ , $r_2=4$ ): The distances from the vertices in $V_1$ to $v_{kt}$ are at most k, and the distances from the vertices in $V_4$ to $v_{kt}$ are $k+1$ , and therefore $v_{kt}$ can resolve u and v.

Case 6 ( $r_1=2$ , $r_2=4$ ): In this case, it is clear that the only vertices with the same metric representations with respect to $W_1$ are the pairs $(v_{tx+t},v_{n-tx-1})$ , where $x=1,2,\ldots ,k-1$ . Since

$$ \begin{align*}d(v_{kt},v_{tx+t})=k-x-1\quad\text{and}\quad d(v_{kt},v_{n-tx-1})=k-x+2, \end{align*} $$

it follows that $v_{kt}\in W_2$ can resolve all these pairs.

Proof Let

$$ \begin{align*} &W_1=\{v_0,v_2,\ldots,v_{t-1}\}, W_2=\{v_{n-(t-1)},v_{n-(t-3)},\ldots,v_{n-2}\},\\ &W_3=\{v_{kt+1},v_{kt+3},\ldots,v_{kt+p-2}\}, \end{align*} $$

where $\sharp (W_1)=\frac {t+1}{2}$ , $\sharp (W_2)=\frac {t-1}{2}$ , and $\sharp (W_3)=\frac {p-1}{2}$ . Let us show that $W=W_1\cup W_2\cup W_3$ is a resolving set of the graph $C_n(1,2,\ldots ,t)$ . As before, divide the vertex set of $C_n(1,2,\ldots ,t)$ into four disjoint sets:

$$ \begin{align*} &V_1=\{v_0,v_1,\ldots,v_t\}, V_2=\{v_{t+1},v_{t+2},\ldots,v_{kt-1},v_{kt}\},\\ &V_3=\{v_{kt+1},v_{kt+2},\ldots,v_{kt+t+p-2},v_{kt+t+p-1}\},V_4=\{v_{kt+t+p},v_{kt+t+p+1},\ldots,v_{n-2},v_{n-1}\}. \end{align*} $$

We claim that any pair of distinct vertices $u\in V_{r_1}$ and $v\in V_{r_2}$ have different metric representations with respect to W, and only consider six cases.

Case 1 ( $r_1=r_2=1$ ): We need only show that no two vertices in $V_1\backslash W_1=\{v_j:j=1,3,\ldots ,t\}$ have the same metric representation with respect to $W_2$ . Observe that for $j=1,3,\ldots ,t$ , $r(v_j|W_2)=(2,\ldots ,2,1,\ldots ,1)$ , of which the first $\frac {j-1}{2}$ entries are equal to $2$ , and the other $\frac {t-j}{2}$ entries are equal to $1$ , the desired result follows.

Case 2 ( $r_1=r_2=2$ ): It is easy to verify that, for $x=1,\ldots ,k-1$ and $j=1,2,\ldots ,t$ , the metric representation of $v_{tx+j}\in V_2$ with respect to $W_1$ is

$$ \begin{align*}r(v_{tx+j}|W_1)=(\underbrace{x+1,\ldots,x+1}_{\left\lceil\frac{j}{2}\right\rceil},\underbrace{x,\ldots,x}_{\frac{t+1}{2}-\left\lceil\frac{j}{2}\right\rceil}). \end{align*} $$

Hence, the only vertices in $V_2$ with the same metric representations with respect to $W_1$ are the pairs $(v_{tx+j},v_{tx+j+1})$ , where $j=1,3,\ldots ,t-2$ and $x=1,2,\ldots ,k-1$ . Since $v_{n-t+j}$ belongs to $W_2$ for each $j\in \{1,3,\ldots ,t-2\}$ , and since

$$ \begin{align*}d(v_{n-t+j},v_{tx+j})=x+1\quad\text{and}\quad d(v_{n-t+j},v_{tx+j+1})=x+2, \end{align*} $$

it follows that $W_2$ can distinguish these pairs.

Case 3 ( $r_1=r_2=3$ ): The metric representations of the vertices in $V_3$ with respect to $W_1$ and $W_2$ are the following:

$$ \begin{align*} &r(v_{kt+j}|W_1)=(\overbrace{k+1,\ldots,k+1}^{\left\lceil\frac{j}{2}\right\rceil},\overbrace{k,\ldots,k}^{\frac{t+1}{2}-\left\lceil\frac{j}{2}\right\rceil}) \quad\text{for}\,\, j=1,2,\ldots,t-1, \\ &r(v_{kt+j}|W_1)=(k+1,\ldots,k+1)\quad\text{for}\,\, j=t,t+1,\ldots,t+p-1,\\ &r(v_{kt+j}|W_2)=(k+1,\ldots,k+1)\quad\text{for}\,\, j=1,2,\ldots,p-1,\\ &r(v_{kt+j}|W_2)=(\underbrace{k,\ldots,k}_{\left\lceil\frac{j-p}{2}\right\rceil},\underbrace{k+1,\ldots,k+1}_{\frac{t-1}{2}-\left\lceil\frac{j-p}{2}\right\rceil})\quad\text{for}\,\, j=p,p+1,\ldots,t+p-1. \end{align*} $$

Write $u=v_{kt+j_1}$ and $v=v_{kt+j_2}$ . There are two subcases to consider.

Case 3.1 ( $j_1<t$ , $j_2<t$ ): In this case, the only vertices with the same metric representations with respect to $W_1$ are the pairs $(v_{kt+j},v_{kt+j+1})$ , where $j=1,3,\ldots ,t-2$ . If $p=t$ , then $W_3$ can already distinguish all the pairs. Suppose now that $p\leq t-2$ . In view of the definition of $W_3$ , it is sufficient to show that $(v_{kt+j},v_{kt+j+1})$ can be distinguished by $W_2$ for $j=p,p+2,\ldots ,t-2$ . Noticing that $v_{2kt+j+1}$ belongs to $W_2$ for each $j\in \{p,p+2,\ldots ,t-2\}$ , and that

$$ \begin{align*}d(v_{2kt+j+1},v_{kt+j})=k+1\quad\text{and}\quad d(v_{2kt+j+1},v_{kt+j+1})=k, \end{align*} $$

the desired result follows.

Case 3.2 ( $j_1\geq t$ , $j_2\geq t$ ): In this case, the only vertices with the same metric representations with respect to $W_2$ are the pairs $(v_{kt+t+j},v_{kt+t+j+1})$ , where $j=1,3,\ldots , p-2$ . Since $v_{kt+j}$ belongs to $W_3$ for each $j\in \{1,3,\ldots ,p-2\}$ , and since

$$ \begin{align*}d(v_{kt+t+j},v_{kt+j})=1\quad\text{and}\quad d(v_{kt+t+j+1},v_{kt+j})=2, \end{align*} $$

it follows that $W_3$ can distinguish these pairs.

Case 4 ( $r_1=r_2=4$ ): For $x=1,2,\ldots ,k$ and $j=0,1,\ldots ,t-1$ , the metric representation of $v_{n-tx+j}\in V_4$ with respect to $W_1$ is

$$ \begin{align*}r(v_{n-tx+j}|W_1)=(\underbrace{x,\ldots,x}_{\left\lfloor\frac{j}{2}\right\rfloor+1},\underbrace{x+1,\ldots,x+1}_{\frac{t-1}{2}-\left\lfloor\frac{j}{2}\right\rfloor}). \end{align*} $$

Hence, the only vertices in $V_4$ with the same metric representations with respect to $W_1$ are the pairs $(v_{n-tx+j-1},v_{n-tx+j})$ , where $j=1,3,\ldots ,t-2$ and $x=1,2,\ldots ,k$ . Since $v_{n-t+j}$ belongs to $W_2$ for each $j\in \{1,3,\ldots ,t-2\}$ , and since

$$ \begin{align*}d(v_{n-tx+j},v_{n-t+j})=x-1\quad\text{and}\quad d(v_{n-tx+j-1},v_{n-t+j})=x, \end{align*} $$

it follows that $W_2$ can distinguish all these pairs.

Case 5 ( $r_1=1$ , $r_2=4$ ): In this case, the only vertices with the same metric representations with respect to $W_1$ are the pairs $(v_{n-1},v_{j})$ , where $j=1,3,\ldots ,t$ , which can be resolved by $v_{kt+1}\in W_3$ .

Case 6 ( $r_1=2$ , $r_2=4$ ): In this case, the only vertices with the same metric representations with respect to $W_1$ are the pairs $(v_{tx+t},v_{n-tx-1})$ , where $x=1,2,\ldots ,k-1$ . Note that $v_{n-2}$ belongs to $W_2$ , and that

$$ \begin{align*}d(v_{tx+t},v_{n-2})=x+2\quad\text{and}\quad d(v_{n-tx-1},v_{n-2})=x. \end{align*} $$

Therefore, $W_2$ can distinguish these pairs. This completes our proof.