On the metric dimension of circulant graphs

Abstract

In this note, we bound the metric dimension of the circulant graphs $C_n(1,2,\ldots ,t)$. We shall prove that if $n=2tk+t$ and if t is odd, then $\dim (C_n(1,2,\ldots ,t))=t+1$, which confirms Conjecture 4.1.1 in Chau and Gosselin (2017, Opuscula Mathematica 37, 509–534). In Vetrík (2017, Canadian Mathematical Bulletin 60, 206–216; 2020, Discussiones Mathematicae. Graph Theory 40, 67–76), the author has shown that $\dim (C_n(1,2,\ldots ,t))\leq t+\left \lceil \frac {p}{2}\right \rceil $ for $n=2tk+t+p$, where $t\geq 4$ is even, $1\leq p\leq t+1$, and $k\geq 1$. Inspired by his work, we show that $\dim (C_n(1,2,\ldots ,t))\leq t+\left \lfloor \frac {p}{2}\right \rfloor $ for $n=2tk+t+p$, where $t\geq 5$ is odd, $2\leq p\leq t+1$, and $k\geq 2$.

1 Introduction

Let $G=(V(G),E(G))$ be a simple undirected connected graph. The distance $d(u,v)$ between two vertices u and v in G is the length of a shortest path between these two vertices. For an ordered set $W=\{w_1,\ldots ,w_k\}$ of k distinct vertices of G, we refer to the k-tuple $r(v|W)=(d(v,w_1),d(v,w_2),\ldots ,d(v,w_k))$ as the metric representation of a vertex v with respect to W. The set W is called a resolving set of G if $r(u|W)=r(v|W)$ implies that $u=v$ for all $u,v\in V(G)$ . A resolving set containing a minimum number of vertices is called a metric basis of G, and its cardinality the metric dimension of G, denoted by $\mathrm {dim}(G)$ .

Motivated by the problem of uniquely determining the location of an intruder in a network, Slater introduced the notion of metric dimension of a graph in [9], where the resolving sets were referred to as locating sets. Harary and Melter also introduced the idea of the metric dimension of a graph in [5]. It was proved that the metric dimension is an NP-hard graph invariant [8] and has been widely investigated in the last 55 years and it also has applications in many diverse areas [6, 7].

This note is devoted to the study of the metric dimension of circulant graphs. Let n, t, and $a_1,a_2,\ldots ,a_t$ be positive integers so that $1\leq a_1<a_2<\dots <a_t\leq \left \lfloor \frac {n}{2}\right \rfloor $ . The circulant graph $C_n(a_1,a_2,\ldots ,a_t)$ consists of a vertex set $\{v_0,v_1,\ldots ,v_{n-1}\}$ and an edge set $\{v_iv_{i+a_j}:0\leq i\leq n-1,1\leq j\leq t\}$ , where the indices are taken modulo n. The numbers $a_1,a_2,\ldots ,a_t$ are called generators. We restrict our attention to special kinds of circulant graphs, i.e., the circulant graphs $C_n(1,2,\ldots ,t)$ with consecutive generators. In [1], Borchert and Gosselin studied the metric dimension of $C_n(1,2)$ and $C_n(1,2,3)$ , and obtained that for $n\geq 6$ ,

$$ \begin{align*} \dim(C_n(1,2))=\left\{ \begin{aligned} &4,\quad & \text{for}\,\, n\equiv1 \,\,\text{mod}\,\, 4, \\ &3,\quad & \text{otherwise,}\,\, \end{aligned} \right. \end{align*} $$

and that for $n\geq 8$ ,

$$ \begin{align*} \dim(C_n(1,2,3))=\left\{ \begin{aligned} &5,\quad & \text{for}\,\, n\equiv1 \,\,\text{mod}\,\, 6, \\ &4,\quad & \text{otherwise.}\,\, \end{aligned} \right. \end{align*} $$

In [3, 11], the authors studied the metric dimension of $C_n(1,2,3,4)$ , and obtained that for $n\geq 20$ ,

$$ \begin{align*} \dim(C_n(1,2,3,4))=\left\{ \begin{aligned} &6,\quad & \text{for}\,\, n\equiv0,1,7 \,\,\text{mod}\,\, 8, \\ &5,\quad & \text{for}\,\, n\equiv2,3,5,6 \,\,\text{mod}\,\, 8, \\ &4,\quad & \text{for}\,\, n\equiv4 \,\,\text{mod}\,\, 8. \end{aligned} \right. \end{align*} $$

For the results concerning $\dim (C_n(1,2,\ldots ,t))$ with arbitrary integers $t\geq 5$ , the reader may refer to [2, 4, 10, 12].

We shall assume throughout this note that $n=2tk+r$ , where $t\geq 4$ , $k\geq 2$ , and $2\leq r\leq 2t+1$ . When $t\leq r\leq 2t+1$ , we may also assume $n=2tk+t+p$ , where $0\leq p\leq t+1$ . It is known that the distance between two vertices $v_i$ and $v_j$ in $C_n(1,2,\ldots ,t)$ is

(1.1) $$ \begin{align} d(v_i,v_j)=\min\left\{\left\lceil\frac{|i-j|}{t}\right\rceil,\left\lceil\frac{n-|i-j|}{t}\right\rceil\right\}, \end{align} $$

and that the diameter of $C_n(1,2,\ldots ,t)$ is $d:= k+1$ .

Here, we set forth our notation and terminology. Let W and V be subsets of vertices in $G=C_n(1,2,\ldots ,t)$ , where V consists of at least two vertices. A vertex w is said to resolve a pair of vertices u and v if $d(u,w)\neq d(v,w)$ . W is said to distinguish V if for any pair of distinct vertices u and v in V, there exists a vertex in W which can resolve u and v. It is easy to see that if W can distinguish $V(G)$ , then it is a resolving set of G. Vertices $v_{i+1},v_{i+2},\ldots ,v_{i+s}$ with consecutive indices are called the consecutive vertices. The outer cycle of the circulant graph is a spanning subgraph of G in which the vertex $v_i$ is adjacent to exactly the vertices $v_{i+1}$ and $v_{i-1}$ . When $r=2$ , the unique vertex that has distance $k+1$ from w will be called the opposite vertex of w, and is denoted by $w^{'}$ , and we can then define $W^{'}:=\{w^{'}:w\in W\}$ for the vertex set W.

2 Lower bounds

This section deals with the lower bounds for $\dim (C_n(1,2,\ldots ,t))$ . In [2, 10], the authors have shown that when $3\leq r\leq t$ and n is sufficiently large, $\dim (C_n(1,2,\ldots ,t))$ has a lower bound of t.

Theorem 2.1 ([10, Theorem 2.3]) Let $n=2tk+r$ where $3\leq r\leq t$ , and $n\geq t^2+1$ . Then $\dim (C_n(1,2,\ldots ,t))\geq t$ .

Theorem 2.3 improves their result. We begin with the following lemma.

Lemma 2.2 Suppose that $r=t$ , and that $2\leq x\leq t$ . If a vertex set W can distinguish x consecutive vertices, then the cardinality of W is at least $x-1$ .

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$ .

Theorem 2.3 Let $n=2tk+t$ where t is odd. Then $\dim (C_n(1,2,\ldots ,t))\geq t+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.

In what follows, we shall discuss the case where $r\in \{2\}\cup \{t+1,t+2,\ldots ,2t+1\}$ . The following lemma will be needed in the sequel.

Lemma 2.4 Suppose that $r\in \{2\}\cup \{t+1,t+2,\ldots ,2t+1\}$ and that $2\leq x\leq t$ . If a vertex set W can distinguish x vertices which come from a clique of $x+1$ consecutive vertices, then the cardinality of W is at least $x-1$ .

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$ .

The authors showed in [2] that $\dim (C_n(1,2,\ldots ,t))$ has a lower bound of $t+1$ if $r\in \{2\}\cup \{t+1,t+2,\ldots ,2t\}$ . We provide an alternate proof.

Theorem 2.5 ([2, Theorem 2.7]) Let $n=2tk+r$ where $r\in \{2\}\cup \{t+1,t+2,\ldots ,2t\}$ . Then $\dim (C_n(1,2,\ldots ,t))\geq t+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$ .

In [2], the authors have shown that when $r=2t+1$ , $\dim (C_n(1,2,\ldots ,t))$ has a lower bound of $t+2$ . We provide an alternate proof.

Theorem 2.6 ([2, Theorem 2.17]) Let $n=2tk+2t+1$ . Then $\dim (C_n(1,2,\ldots ,t))\geq t+2$ .

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.

3 Upper bounds

This section is devoted to the study of upper bounds for $\dim (C_n(1,2,\ldots ,t))$ . The following three theorems provide a great deal of useful information about this topic.

Theorem 3.1 ([4, Theorem 2.9]) Let $n=2tk+r$ where $2\leq r\leq t+1$ . Then

$$ \begin{align*} \dim(C_n(1,2,\ldots,t))\leq t+1. \end{align*} $$

Theorem 3.2 ([10, Theorem 2.1 and Theorem 2.2]) Let $n=2tk+t+p$ where t and p are both even, and $0\leq p\leq t$ . Then

$$ \begin{align*} \dim(C_n(1,2,\ldots,t))\leq t+\frac{p}{2}. \end{align*} $$

Theorem 3.3 ([12, Theorem 5]) Let $n=2tk+t+p$ where t is even, p is odd, and $1\leq p\leq t+1$ . Then

$$ \begin{align*} \dim(C_n(1,2,\ldots,t))\leq t+\frac{p+1}{2}. \end{align*} $$

Motivated by the work of Vetrík, we provide an upper bound on the metric dimension of $C_n(1,2,\ldots ,t)$ , where t is odd and $r\geq t+2$ .

Theorem 3.4 Let $n=2tk+t+p$ where t is odd, p is even, and $2\leq p\leq t+1$ . Then

$$ \begin{align*} \dim(C_n(1,2,\ldots,t))\leq t+\frac{p}{2}. \end{align*} $$

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.

Theorem 3.5 Let $n=2tk+t+p$ where t and p are both odd, and $3\leq p\leq t$ . Then

$$ \begin{align*} \dim(C_n(1,2,\ldots,t))\leq t+\frac{p-1}{2}. \end{align*} $$

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.