The metric dimension of the circulant graph with 



2
k




 generators can be less than k

Tomáš Vetrík; Muhammad Imran; Martin Knor; Riste Škrekovski

doi:10.1016/j.jksus.2023.102834

View/Download PDF

Buy Reprints

PDF

Translate this page into:

Original article

10 2023

:35;

102834

doi:

10.1016/j.jksus.2023.102834

The metric dimension of the circulant graph with $2 k$ generators can be less than k

Tomáš Vetrík^{^a}, Muhammad Imran^{^b,⁎}, Martin Knor^{^c}, Riste Škrekovski^{^d,^e}

a Department of Mathematics and Applied Mathematics, University of the Free State, Bloemfontein, South Africa

b Department of Mathematical Sciences, Colleges of Science, United Arab Emirates University, Al Ain, United Arab Emirates

c Slovak University of Technology, Bratislava, Slovakia

d Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia

e Faculty of Information Studies, Novo Mesto, Slovenia

⁎Corresponding author. imrandhab@gmail.com (Muhammad Imran),

Received: 2022-10-13, Accepted: 2023-7-30,

Disclaimer:
This article was originally published by Elsevier and was migrated to Scientific Scholar after the change of Publisher.

Peer review under responsibility of King Saud University.

Abstract

Circulant graphs are useful networks because of their symmetries. For $k ⩾ 2$ and $n ⩾ 2 k + 1$ , the circulant graph $C_{n} (1, 2, \dots, k)$ consists of the vertices $v_{0}, v_{1}, v_{2}, \dots, v_{n - 1}$ and the edges $v_{i} v_{i + 1}, v_{i} v_{i + 2}, \dots, v_{i} v_{i + k}$ , where $i = 0, 1, 2, \dots, n - 1$ , and the subscripts are taken modulo n. The metric dimension $β (C_{n} (1, 2, \dots, k))$ of the circulant graphs $C_{n} (1, 2, \dots, k)$ for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that $β (C_{n} (1, 2, \dots, k)) ⩾ k$ for every k, and they conjectured that if $n = 2 k + r$ , where k is even and $3 ⩽ r ⩽ k - 1$ , then $β (C_{n} (1, 2, \dots, k)) = k$ . We disprove both by showing that for every $k ⩾ 9$ , there exists an $n \in [2 k + 5, 2 k + 8] \subset [2 k + 3, 3 k - 1]$ such that $β (C_{n} (1, 2, \dots, k)) ⩽ ⌈\frac{2 k}{3}⌉ + 2$ . We conjecture that for $k ⩾ 6, β (C_{n} (1, 2, \dots, k))$ cannot be less than $⌈\frac{2 k}{3}⌉ + 2$ .

Keywords

Metric dimension

Resolving set

Distance

Cayley graph

Circulant graph

Show Related Articles from PubMed

1 Introduction

The metric dimension is an invariant which has applications in pharmaceutical chemistry (see Chartrand et al., 2000), pattern recognition and image processing (see Melter and Tomescu, 1984), robot navigation (see Khuller et al., 1996), and Sonar and coast guard Loran (see Slater, 1975).

In a graph G having vertex set $V (G)$ , the number of edges in a shortest path connecting two vertices $u, v \in V (G)$ is the distance $d (u, v)$ between u and v. If $d (u, w) \neq d (v, w)$ , then a vertex w resolves two vertices u and v. For an ordered set $W = {w_{1}, w_{2}, \dots, w_{z}}$ , the ordered z-tuple $r (v | W) = (d (v, w_{1}), d (v, w_{2}), \dots, d (v, w_{z}))$ is the representation of distances of v in terms of W. If all the vertices of G have different representations, then $W \subset V (G)$ is a resolving set of G. The metric dimension $β (G)$ is the number of vertices in a smallest resolving set.

Circulant graphs are very useful networks because of their symmetries. For $k ⩾ 2$ and $n ⩾ 2 k + 1$ , the circulant graph $C_{n} (1, 2, \dots, k)$ has the vertices $v_{0}, v_{1}, v_{2}, \dots, v_{n - 1}$ and the edges $v_{i} v_{i + 1}, v_{i} v_{i + 2}, \dots, v_{i} v_{i + k}$ , where $i = 0, 1, 2, \dots, n - 1$ , and the subscripts are taken modulo n. We assume that $n ⩾ 2 k + 1$ , because for $n ⩽ 2 k, C_{n} (1, 2, \dots, k)$ would contain multiple edges. So, ${\pm 1, \pm 2, \dots, \pm k}$ is the set of generators of $C_{n} (1, 2, \dots, k)$ .

In this paper, we focus on the following question: For a fixed k, find $\min {β (C_{n} (1, 2, \dots, k)) | n ⩾ 2 k + 1} .$ By Borchert and Gosselin (2018) and Javaid et al. (2008), we have $β (C_{n} (1, 2)) = \{\begin{matrix} 4 & if n \equiv 1 (\mod 4), \\ 3 & if n \equiv 0, 2, 3 (\mod 4) . \end{matrix}$ By Borchert and Gosselin (2018) and Imran et al. (2012), for $n ⩾ 8$ , $β (C_{n} (1, 2, 3)) = \{\begin{matrix} 5 & if n \equiv 1 (\mod 6), \\ 4 & if n \equiv 0, 2, 3, 4, 5 (\mod 6) . \end{matrix}$ Since $β (C_{n} (1, 2)) ⩾ 3$ and $β (C_{n} (1, 2, 3)) ⩾ 4$ , Grigorious et al. (2014) assumed and proved that $β (C_{n} (1, 2, \dots, k)) ⩾ k + 1$ . Their result does not hold. In Vetrík (2017) it was proved that $β (C_{n} (1, 2, \dots, k))$ can be k, and that for $n ⩾ k^{2} + 1$ where $k ⩾ 2$ , $β (C_{n} (1, 2, \dots, k)) ⩾ k,$ and for $n \equiv r (\mod 2 k)$ where $k + 2 ⩽ r ⩽ 2 k + 1$ and $k ⩾ 2$ , we have $β (C_{n} (1, 2, \dots, k)) ⩾ k + 1 .$ Chau and Gosselin (2017) obtained several strong results, but their inequality (1) is incorrect. They proved that for $n \equiv r (\mod 2 k)$ ,

(1)

β (C_{n} (1, 2, \dots, k)) ⩾ k

3 ⩽ r ⩽ k

, and

β (C_{n} (1, 2, \dots, k)) ⩾ k + 1

k + 1 ⩽ r ⩽ 2 k + 2

. They also conjectured that if

n = 2 k + r

where k is even and

3 ⩽ r ⩽ k - 1

, then

(2)

β (C_{n} (1, 2, \dots, k)) = k .

We disprove (1) and (2) by showing that for every

k ⩾ 9

, there exists an

n \in [2 k + 5, 2 k + 8] \subset [2 k + 3, 3 k - 1]

such that

β (C_{n} (1, 2, \dots, k)) ⩽ ⌈\frac{2 k}{3}⌉ + 2 .

The importance of this result is that it has not been known before that

β (C_{n} (1, 2, \dots, k))

can be less than k.

Let us note that the graphs $C_{n} (1, 3)$ were studied in Javaid et al. (2012), $C_{n} (1, 4)$ in Azhar and Javaid (2018), $C_{n} (2, 3)$ in Du Toit and Vetrík (2019), $C_{n} (1, \frac{n}{2})$ for even n in Salman et al. (2012), $C_{n} (1, 2, 4)$ in Imran and Bokhary (2014), $C_{n} (1, 2, 5)$ in Imran et al. (2018), $C_{n} (1, 2, 3, 4)$ in Grigorious et al. (2017) and Vetrík (2017), $C_{n} (1, 2, \dots, k)$ also in Vetrík (2020), and some interesting networks were investigated also in Arulperumjothi et al. (2023), Azeem et al. (2022), Koam et al. (2022), Prabhu et al. (2022) and Prabhu et al. (2022).

2 New bounds

We show that for every $k ⩾ 7$ , there exists an n such that $β (C_{n} (1, 2, \dots, k)) ⩽ ⌈\frac{2 k}{3}⌉ + 2$ . The case $k \equiv 1 (\mod 3)$ is studied in Theorem 1, $k \equiv 2 (\mod 6)$ is studied in Theorem 2, $k \equiv 3 (\mod 6)$ is investigated in Theorem 3, $k \equiv 5 (\mod 6)$ is considered in Theorem 4 and $k \equiv 0 (\mod 6)$ is studied in Theorem 5. Note that the subscripts of the vertices $v_{i}$ are taken modulo n.

Theorem 1

Let $n = 2 k + 5$ where $k \equiv 1 (\mod 3)$ such that $k ⩾ 7$ . Then $β (C_{n} (1, 2, \dots, k)) ⩽ \frac{2 k + 1}{3} + 2 .$

Proof

Let $W = {v_{0}} \cup {v_{i} : i = 2, 5, \dots, 2 k + 3}$ . We have $n = 2 k + 5$ , so for any vertex $v_{i} \in W$ (where $i = 2, 5, \dots, 2 k + 3$ or 0), there are 4 vertices $v_{i + k + 1}, v_{i + k + 2}, v_{i + k + 3}, v_{i + k + 4}$ at distance 2 from $v_{i}$ (and $2 k$ vertices at distance 1 from $v_{i}$ ). Let $V_{i} = {v_{i + k + 1}, v_{i + k + 2}, v_{i + k + 3}, v_{i + k + 4}}$ . It follows that the representations of a vertex of $V (C_{n} (1, 2, \dots, k)) ⧹ V_{i}$ and a vertex of $V_{i}$ are not the same in terms of W.

For the vertices of $V_{i}$ where $i = 5, 8, \dots, 2 k$ and the ordered set ${v_{i - 3}, v_{i + 3}} \subset W$ , we get $\begin{matrix} r (v_{i + k + 1} | {v_{i - 3}, v_{i + 3}}) = (2, 1), \\ r (v_{i + k + 2} | {v_{i - 3}, v_{i + 3}}) = (1, 1), \\ r (v_{i + k + 3} | {v_{i - 3}, v_{i + 3}}) = (1, 1), \\ r (v_{i + k + 4} | {v_{i - 3}, v_{i + 3}}) = (1, 2) . \end{matrix}$ Since $v_{i + k + 2} \in W$ for $i = 5, 8, \dots, k + 1$ , and $v_{i + k + 3} \in W$ for $i = k + 4, k + 7, \dots, 2 k$ , the vertices of $V_{i}$ are resolved (for $i = 5, 8, \dots, 2 k$ ). We have $V_{5} \cup V_{8} \cup \dots \cup V_{2 k} = {v_{k + 6}, v_{k + 7}, \dots, v_{3 k + 4}} .$ Note that $3 k + 4 = k - 1$ . Finally, we need to resolve $v_{k}, v_{k + 1}, \dots, v_{k + 5}$ . We have $v_{k + 1}, v_{k + 4} \in W$ and $\begin{matrix} r (v_{k} | {v_{2 k + 3}, v_{0}, v_{2}}) = (2, 1, 1), \\ r (v_{k + 2} | {v_{2 k + 3}, v_{0}, v_{2}}) = (2, 2, 1), \\ r (v_{k + 3} | {v_{2 k + 3}, v_{0}, v_{2}}) = (1, 2, 2), \\ r (v_{k + 5} | {v_{2 k + 3}, v_{0}, v_{2}}) = (1, 1, 2) . \end{matrix}$ Thus all the vertices of $C_{n} (1, 2, \dots, k)$ are resolved. So, W is a resolving set and we obtain $β (C_{n} (1, 2, \dots, k)) ⩽ | W | = \frac{2 k + 1}{3} + 2$ . □

Theorem 2

Let $n = 2 k + 8$ where $k \equiv 2 (\mod 6)$ such that $k ⩾ 8$ . Then $β (C_{n} (1, 2, \dots, k)) ⩽ \frac{2 k + 2}{3} + 2 .$

Proof

For $i = 0, 1, 2, \dots, \frac{k + 1}{3}$ , let $W_{i} = {v_{6 i}, v_{6 i + 2}}$ . We show that $W = W_{0} \cup W_{1} \cup \dots \cup W_{\frac{k + 1}{3}}$ resolves $C_{n} (1, 2, \dots, k)$ . We have $n = 2 k + 8$ , so for any vertex $v_{j}$ where $j = 0, 1, \dots, n - 1$ , there are 7 vertices $v_{j + k + 1}, v_{j + k + 2}, v_{j + k + 3}, v_{j + k + 4}, v_{j + k + 5}, v_{j + k + 6}, v_{j + k + 7}$ at distance 2 from $v_{j}$ (and $2 k$ vertices at distance 1 from $v_{j}$ ). Thus there are exactly 7 vertices at distance 2 from $v_{6 i} \in W_{i}$ where $i = 0, 1, 2, \dots, \frac{k + 1}{3}$ . Those vertices are the vertices of the set $V_{i} = {v_{6 i + k + 1}, v_{6 i + k + 2}, v_{6 i + k + 3}, v_{6 i + k + 4}, v_{6 i + k + 5}, v_{6 i + k + 6}, v_{6 i + k + 7}} .$ So, the representations of a vertex of $V (C_{n} (1, 2, \dots, k)) ⧹ V_{i}$ and a vertex of $V_{i}$ are not the same in terms of W. For the vertices of $V_{i}$ and ${v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}} \subset W$ , we get $\begin{matrix} r (v_{6 i + k + 1} | {v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}}) = (2, 2, 1, 1), \\ r (v_{6 i + k + 2} | {v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 1, 1), \\ r (v_{6 i + k + 3} | {v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 4} | {v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 1), \\ r (v_{6 i + k + 5} | {v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 1), \\ r (v_{6 i + k + 6} | {v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 1), \\ r (v_{6 i + k + 7} | {v_{6 i - 6}, v_{6 i - 4}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 2) . \end{matrix}$ The vertices $v_{6 i + k + 4}, v_{6 i + k + 6} \in W$ , so the vertices of $V_{i}$ are resolved (where $i = 0, 1, 2, \dots, \frac{k + 1}{3}$ ). Since $V_{0} \cup V_{1} \cup \dots \cup V_{\frac{k + 1}{3}} = V (C_{n} (1, 2, \dots, k))$ , the set W resolves the vertices of $C_{n} (1, 2, \dots, k)$ . Therefore $β (C_{n} (1, 2, \dots, k)) ⩽ | W | = 2 (\frac{k + 1}{3} + 1)$ . □

Theorem 3

Let $n = 2 k + 6$ where $k \equiv 3 (\mod 6)$ such that $k ⩾ 9$ . Then $β (C_{n} (1, 2, \dots, k)) ⩽ \frac{2 k}{3} + 2 .$

Proof

For $i = 0, 1, 2, \dots, \frac{k}{3}$ , let $W_{i} = {v_{6 i}, v_{6 i + 2}}$ . We show that $W = W_{0} \cup W_{1} \cup \dots \cup W_{\frac{k}{3}}$ resolves $C_{n} (1, 2, \dots, k)$ . We have $n = 2 k + 6$ , so for any vertex $v_{j}$ where $j = 0, 1, \dots, n - 1$ , there are 5 vertices $v_{j + k + 1}, v_{j + k + 2}, v_{j + k + 3}, v_{j + k + 4}, v_{j + k + 5}$ at distance 2 from $v_{j}$ . For each $W_{i} = {v_{6 i}, v_{6 i + 2}}$ where $i = 0, 1, 2, \dots, \frac{k}{3}$ , there are 7 vertices at distance 2 from at least one of $v_{6 i}, v_{6 i + 2}$ . Those vertices are the vertices of the set $V_{i} = {v_{6 i + k + 1}, v_{6 i + k + 2}, v_{6 i + k + 3}, v_{6 i + k + 4}, v_{6 i + k + 5}, v_{6 i + k + 6}, v_{6 i + k + 7}} .$ So, the representations of a vertex of $V (C_{n} (1, 2, \dots, k)) ⧹ V_{i}$ and a vertex of $V_{i}$ are not the same in terms of W. For the vertices of $V_{i}$ and the ordered set ${v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}} \subset W$ , we get $\begin{matrix} r (v_{6 i + k + 1} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (2, 2, 1, 1), \\ r (v_{6 i + k + 2} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 1, 1), \\ r (v_{6 i + k + 3} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 4} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 5} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 6} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 1), \\ r (v_{6 i + k + 7} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 2) . \end{matrix}$ The vertices $v_{6 i + k + 3}, v_{6 i + k + 5} \in W$ , so the vertices of $V_{i}$ are resolved (where $i = 0, 1, 2, \dots, \frac{k}{3}$ ). Since $V_{0} \cup V_{1} \cup \dots \cup V_{\frac{k}{3}} = V (C_{n} (1, 2, \dots, k))$ , W resolves the vertices of $C_{n} (1, 2, \dots, k)$ . Therefore $β (C_{n} (1, 2, \dots, k)) ⩽ | W | = 2 (\frac{k}{3} + 1)$ . □

Theorem 4

Let $n = 2 k + 6$ where $k \equiv 5 (\mod 6)$ such that $k ⩾ 11$ . Then $β (C_{n} (1, 2, \dots, k)) ⩽ \frac{2 k + 2}{3} + 2 .$

Proof

For $i = 0, 1, 2, \dots, \frac{k - 5}{6}$ , let $W_{i} = {v_{6 i}, v_{6 i + 2}}$ and $W_{i}^{'} = {v_{6 i + k + 3}, v_{6 i + k + 5}}$ . Let $W^{'} = {v_{k - 1}, v_{2 k + 2}}$ and $W = (W_{0} \cup W_{1} \cup \dots \cup W_{\frac{k - 5}{6}}) \cup (W_{0}^{'} \cup W_{1}^{'} \cup \dots \cup W_{\frac{k - 5}{6}}^{'}) \cup W^{'} .$ Note that $| W | = 2 (\frac{k - 5}{6} + 1) + 2 (\frac{k - 5}{6} + 1) + 2 = \frac{2 k + 2}{3} + 2$ . We prove that W resolves $C_{n} (1, 2, \dots, k)$ . We have $n = 2 k + 6$ , so for any vertex $v_{j}$ where $j = 0, 1, \dots, n - 1$ , there are 5 vertices $v_{j + k + 1}, v_{j + k + 2}, v_{j + k + 3}, v_{j + k + 4}, v_{j + k + 5}$ at distance 2 from $v_{j}$ .

For each $W_{i} = {v_{6 i}, v_{6 i + 2}}$ where $i = 0, 1, 2, \dots, \frac{k - 5}{6}$ , there are exactly 7 vertices at distance 2 from at least one of $v_{6 i}, v_{6 i + 2}$ . Those vertices are the vertices of the set $V_{i} = {v_{6 i + k + 1}, v_{6 i + k + 2}, v_{6 i + k + 3}, v_{6 i + k + 4}, v_{6 i + k + 5}, v_{6 i + k + 6}, v_{6 i + k + 7}} .$ So, the representations of a vertex in $V (C_{n} (1, 2, \dots, k)) ⧹ V_{i}$ and a vertex of $V_{i}$ are not the same in terms of W. For the vertices of $V_{i}$ where $i = 0, 1, 2, \dots, \frac{k - 11}{6}$ in terms of the ordered set ${v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}} \subset W$ , we get $\begin{matrix} r (v_{6 i + k + 1} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (2, 2, 1, 1), \\ r (v_{6 i + k + 2} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 1, 1), \\ r (v_{6 i + k + 3} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 4} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 5} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 6} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 1), \\ r (v_{6 i + k + 7} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 2) . \end{matrix}$ The vertices $v_{6 i + k + 3}, v_{6 i + k + 5} \in W$ , so the vertices of $V_{i}$ are resolved by W (where $i = 0, 1, 2, \dots, \frac{k - 11}{6}$ ).

Similarly, for each $W_{i}^{'} = {v_{6 i + k + 3}, v_{6 i + k + 5}}$ where $i = 0, 1, 2, \dots, \frac{k - 5}{6}$ , there are exactly 7 vertices at distance 2 from at least one of $v_{6 i + k + 3}, v_{6 i + k + 5}$ . Those vertices are the vertices of the set $V_{i}^{'} = {v_{6 i - 2}, v_{6 i - 1}, v_{6 i}, v_{6 i + 1}, v_{6 i + 2}, v_{6 i + 3}, v_{6 i + 4}} .$ So, the representations of a vertex of $V_{i}^{'}$ and a vertex of $V (C_{n} (1, 2, \dots, k)) ⧹ V_{i}^{'}$ are not the same in terms of W. For the vertices of $V_{i}^{'}$ where $i = 0, 1, 2, \dots, \frac{k - 11}{6}$ in terms of the ordered set ${v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}} \subset W$ , we get $\begin{matrix} r (v_{6 i - 2} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (2, 2, 1, 1), \\ r (v_{6 i - 1} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 1, 1), \\ r (v_{6 i} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 2, 1), \\ r (v_{6 i + 1} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 2, 1), \\ r (v_{6 i + 2} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 2, 1), \\ r (v_{6 i + 3} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 1, 2, 1), \\ r (v_{6 i + 4} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 1, 2, 2) . \end{matrix}$ The vertices $v_{6 i}, v_{6 i + 2} \in W$ , so the vertices of $V_{i}^{'}$ are resolved (where $i = 0, 1, 2, \dots, \frac{k - 11}{6}$ ).

We have $V_{0} \cup V_{1} \cup \dots \cup V_{\frac{k - 11}{6}} = {v_{k + 1}, v_{k + 2}, \dots, v_{2 k - 4}}$ and $V_{0}^{'} \cup V_{1}^{'} \cup \dots \cup V_{\frac{k - 11}{6}}^{'} = {v_{2 k + 4}, v_{2 k + 5}, v_{0}, v_{1} \dots, v_{k - 7}} .$ Finally, we resolve the vertices $v_{k - 6}, v_{k - 5}, \dots, v_{k} and v_{2 k - 3}, v_{2 k - 2}, \dots, v_{2 k + 3} .$ Note that $v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}, v_{2 k + 2} \in W$ and $\begin{matrix} r (v_{k - 6} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (1, 1, 1, 2, 1), \\ r (v_{k - 4} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (1, 1, 1, 2, 2), \\ r (v_{k - 2} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (1, 1, 1, 1, 2), \\ r (v_{k} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (1, 1, 1, 1, 1), \\ r (v_{2 k - 3} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (2, 1, 1, 1, 1), \\ r (v_{2 k - 1} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (2, 2, 1, 1, 1), \\ r (v_{2 k + 1} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (1, 2, 2, 1, 1), \\ r (v_{2 k + 3} | {v_{k - 5}, v_{k - 3}, v_{k - 1}, v_{2 k - 2}, v_{2 k}}) = (1, 1, 2, 1, 1) . \end{matrix}$ Thus all the vertices of $C_{n} (1, 2, \dots, k)$ are resolved. So $β (C_{n} (1, 2, \dots, k)) ⩽ | W | = \frac{2 k + 2}{3} + 2$ . □

The proof of Theorem 5 is longer than the previous proofs, because the resolving sets used in the proof of Theorem 5 are not as simple as resolving sets used in the previous proofs.

Theorem 5

Let $n = 2 k + 6$ where $k \equiv 0 (\mod 6)$ such that $k ⩾ 12$ . Then $β (C_{n} (1, 2, \dots, k)) ⩽ \frac{2 k}{3} + 2 .$

Proof

For $i = 0, 1, \dots, \frac{k}{6} - 1$ , let $W_{i} = {v_{6 i}, v_{6 i + 2}}$ . For $i = 1, 2, \dots, \frac{k}{6} - 2$ , let $W_{i}^{'} = {v_{6 i + k + 3}, v_{6 i + k + 5}}$ . Let $W^{'} = {v_{k - 2}, v_{k + 2}, v_{k + 5}, v_{2 k - 3}, v_{2 k}, v_{2 k + 4}}$ and $W = (W_{0} \cup W_{1} \cup \dots \cup W_{\frac{k}{6} - 1}) \cup (W_{1}^{'} \cup W_{2}^{'} \cup \dots \cup W_{\frac{k}{6} - 2}^{'}) \cup W^{'} .$ Note that $| W | = 2 (\frac{k}{6}) + 2 (\frac{k}{6} - 2) + 6 = \frac{2 k}{3} + 2$ . We prove that W resolves $C_{n} (1, 2, \dots, k)$ . We have $n = 2 k + 6$ , so for any vertex $v_{j}$ where $j = 0, 1, \dots, n - 1$ , there are 5 vertices $v_{j + k + 1}, v_{j + k + 2}, v_{j + k + 3}, v_{j + k + 4}, v_{j + k + 5}$ at distance 2 from $v_{j}$ .

For each $W_{i} = {v_{6 i}, v_{6 i + 2}}$ where $i = 1, 2, \dots, \frac{k}{6} - 2$ , there are 7 vertices at distance 2 from at least one of $v_{6 i}, v_{6 i + 2}$ . Those vertices are the vertices of the set $V_{i} = {v_{6 i + k + 1}, v_{6 i + k + 2}, v_{6 i + k + 3}, v_{6 i + k + 4}, v_{6 i + k + 5}, v_{6 i + k + 6}, v_{6 i + k + 7}} .$ So, the representations of a vertex of $V (C_{n} (1, 2, \dots, k)) ⧹ V_{i}$ and a vertex of $V_{i}$ are not the same in terms of W. For the vertices in $V_{i}$ and the ordered set ${v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}} \subset W$ , we get $\begin{matrix} r (v_{6 i + k + 1} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (2, 2, 1, 1), \\ r (v_{6 i + k + 2} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 1, 1), \\ r (v_{6 i + k + 3} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 4} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 5} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 2, 2, 1), \\ r (v_{6 i + k + 6} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 1), \\ r (v_{6 i + k + 7} | {v_{6 i - 4}, v_{6 i}, v_{6 i + 2}, v_{6 i + 6}}) = (1, 1, 2, 2) . \end{matrix}$ The vertices $v_{6 i + k + 3}, v_{6 i + k + 5} \in W$ , so the vertices of $V_{i}$ are resolved by W (where $i = 1, 2, \dots, \frac{k}{6} - 2$ ).

Similarly, for each $W_{i}^{'} = {v_{6 i + k + 3}, v_{6 i + k + 5}}$ where $i = 1, 2, \dots, \frac{k}{6} - 2$ , there are 7 vertices at distance 2 from at least one of $v_{6 i + k + 3}, v_{6 i + k + 5}$ . Those vertices are the vertices of the set $V_{i}^{'} = {v_{6 i - 2}, v_{6 i - 1}, v_{6 i}, v_{6 i + 1}, v_{6 i + 2}, v_{6 i + 3}, v_{6 i + 4}} .$ For the vertices of $V_{i}^{'}$ and the ordered set ${v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}} \subset W$ , we get $\begin{matrix} r (v_{6 i - 2} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (2, 2, 1, 1), \\ r (v_{6 i - 1} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 1, 1), \\ r (v_{6 i} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 2, 1), \\ r (v_{6 i + 1} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 2, 1), \\ r (v_{6 i + 2} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 2, 2, 1), \\ r (v_{6 i + 3} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 1, 2, 1), \\ r (v_{6 i + 4} | {v_{6 i + k - 1}, v_{6 i + k + 3}, v_{6 i + k + 5}, v_{6 i + k + 9}}) = (1, 1, 2, 2) . \end{matrix}$ The vertices $v_{6 i}, v_{6 i + 2} \in W$ , so the vertices of $V_{i}^{'}$ are resolved.

We have $V_{1} \cup V_{2} \cup \dots \cup V_{\frac{k}{6} - 2} = {v_{k + 7}, v_{k + 8}, \dots, v_{2 k - 5}}$ and $V_{1}^{'} \cup V_{2}^{'} \cup \dots \cup V_{\frac{k}{6} - 2}^{'} = {v_{4}, v_{5}, \dots, v_{k - 8}} .$ Finally, we resolve the vertices $v_{k - 7}, v_{k - 6}, \dots, v_{k + 6} and v_{2 k - 4}, v_{2 k - 3}, \dots, v_{2 k + 5} . v_{0}, v_{1}, v_{2}, v_{3}$ if $k ⩾ 18$ , and it remains to resolve all the vertices if $k = 12$ . Note that $v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}, v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2} \in W,$ so those vertices are resolved. We obtain $\begin{matrix} r (v_{k - 7} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (2, 1, 1, 1, 1), \\ r (v_{k - 5} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (2, 2, 1, 1, 1), \\ r (v_{k - 3} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 2, 1, 1, 1), \\ r (v_{k - 1} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 2, 2, 1, 1), \\ r (v_{k} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 1, 2, 1, 1), \\ r (v_{k + 1} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 1, 2, 2, 1), \\ r (v_{k + 3} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 1, 2, 2, 2), \\ r (v_{k + 4} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 1, 1, 2, 2), \\ r (v_{k + 6} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 1, 1, 1, 2) . \end{matrix}$ and $\begin{matrix} r (v_{2 k - 4} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (2, 1, 1, 1, 1), \\ r (v_{2 k - 2} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (2, 2, 1, 1, 1), \\ r (v_{2 k - 1} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (2, 2, 2, 1, 1), \\ r (v_{2 k + 1} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (1, 2, 2, 1, 1), \\ r (v_{2 k + 2} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (1, 1, 2, 1, 1), \\ r (v_{2 k + 3} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (1, 1, 2, 2, 1), \\ r (v_{2 k + 5} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (1, 1, 1, 2, 1), \\ r (v_{1} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (1, 1, 1, 2, 2), \\ r (v_{3} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (1, 1, 1, 1, 2) . \end{matrix}$ For $i = k - 7, k - 5, k - 3, k - 1, k, k + 1, k + 3, k + 4, k + 6$ , we obtain $r (v_{i} | {v_{k - 6}, v_{k - 4}, v_{k - 2}, v_{k + 2}, v_{k + 5}}) = (1, 1, 1, 1, 1),$ and for $i = 2 k - 4, 2 k - 2, 2 k - 1, 2 k + 1, 2 k + 2, 2 k + 3, 2 k + 5, 1, 3$ , $r (v_{i} | {v_{2 k - 3}, v_{2 k}, v_{2 k + 4}, v_{0}, v_{2}}) = (1, 1, 1, 1, 1) .$ Thus all the vertices of $C_{n} (1, 2, \dots, k)$ are resolved for $k ⩾ 18$ .

If $k = 12$ , it remains to consider $v_{4}$ and $v_{19}$ . We have $r (v_{4} | {v_{k + 5}, v_{2 k - 3}}) = r (v_{4} | {v_{17}, v_{21}}) = (2, 2)$ and $r (v_{19} | {v_{2}, v_{k - 6}}) = r (v_{19} | {v_{2}, v_{6}}) = (2, 2) .$ It can be seen above that no other vertex has such representation in terms of the ordered sets ${v_{k + 5}, v_{2 k - 3}}$ and ${v_{2}, v_{k - 6}}$ . So, W resolves all the vertices of $C_{n} (1, 2, \dots, k)$ . Thus $β (C_{n} (1, 2, \dots, k)) ⩽ | W | = \frac{2 k}{3} + 2$ . □

From Theorems 1–5 , we obtain the following corollary.

Corollary 1

For every $k ⩾ 7$ , there exists an $n \in [2 k + 5, 2 k + 8]$ such that $β (C_{n} (1, 2, \dots, k)) ⩽ ⌈\frac{2 k}{3}⌉ + 2 .$

Let us note that for $k = 7$ and 8, we have $⌈\frac{2 k}{3}⌉ + 2 = k$ , so Corollary 1 is important for $k ⩾ 9$ .

3 Concluding remarks and further work

We showed that for every $k ⩾ 7$ , there is an $n \in [2 k + 5, 2 k + 8]$ such that $β (C_{n} (1, 2, \dots, k)) ⩽ ⌈\frac{2 k}{3}⌉ + 2$ . The importance of this result is that it has not been known before that $β (C_{n} (1, 2, \dots, k))$ can be less than k. We believe that $β (C_{n} (1, 2, \dots, k))$ cannot be less than $⌈\frac{2 k}{3}⌉ + 2$ for $k ⩾ 6$ , thus we provide Conjecture 1 as a possible future work. Note that $n ⩾ 2 k + 1$ , otherwise $C_{n} (1, 2, \dots, k)$ would contain multiple edges.

Conjecture 1

For every $k ⩾ 6$ (and $n ⩾ 2 k + 1$ ), $β (C_{n} (1, 2, \dots, k)) ⩾ ⌈\frac{2 k}{3}⌉ + 2 .$

Conjecture 1 would not hold for $k = 4$ and $k = 5$ . For example, for $k = 5$ and $n = 13$ , the set ${v_{0}, v_{1}, v_{2}, v_{4}, v_{5}}$ is one possible resolving set of $C_{13} (1, 2, \dots, 5)$ .

Data availability statement

The data used to find the results are included in this paper.

Author contributions

All the authors contributed equally to this work. All the authors read and approved the final version.

Acknowledgements

The work of T. Vetrík is based on the research supported by DSI-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS), South Africa. Opinions expressed and conclusions arrived at are those of the author and are not necessarily to be attributed to the CoE-MaSS. The work of M. Imran is supported by Asian Universities Alliance (AUA) grant of United Arab Emirates University (Grant No. G00003461). R. Škrekovski and M. Knor acknowledge partial support of the Slovenian research agency ARRS program P1-0383 and ARRS project J1-3002. M. Knor aknowledges partial support by Slovak research grants VEGA 1/0206/20, VEGA 1/0567/22, APVV-17-0428, APVV-19-0308.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References

Arulperumjothi M., Klavžar S., Prabhu S., . Redefining fractal cubic networks and determining their metric dimension and fault-tolerant metric dimension. Appl. Math. Comput.. 2023;452:128037.
[Google Scholar]
Azeem M., Imran M., Nadeem M.F., . Sharp bounds on partition dimension of hexagonal Möbius ladder. J. King Saud Univ. Sci.. 2022;34(2):101779.
[Google Scholar]
Azhar M.N., Javaid I., . Metric basis in circulant networks. Ars Combin.. 2018;136:277-286.
[Google Scholar]
Borchert A., Gosselin S., . The metric dimension of circulant graphs and Cayley hypergraphs. Util. Math.. 2018;106:125-147.
[Google Scholar]
Chartrand G., Eroh L., Johnson M.A., Oellermann O.R., . Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math.. 2000;105(1–3):99-113.
[Google Scholar]
Chau K., Gosselin S., . The metric dimension of circulant graphs and their Cartesian products. Opuscula Math.. 2017;37(4):509-534.
[Google Scholar]
Du Toit L., Vetrík T., . On the metric dimension of circulant graphs with 2 generators. Kragujevac J. Math.. 2019;43(1):49-58.
[Google Scholar]
Grigorious C., Kalinowski T., Ryan J., Stephen S., . The metric dimension of the circulant graph $C (n, \pm {1, 2, 3, 4})$ . Australas. J. Combin.. 2017;69(3):417-441.
[Google Scholar]
Grigorious C., Manuel P., Miller M., Rajan B., Stephen S., . On the metric dimension of circulant and Harary graphs. Appl. Math. Comput.. 2014;248:47-54.
[Google Scholar]
Imran M., Baig A.Q., Bokhary S.A., Javaid I., . On the metric dimension of circulant graphs. Appl. Math. Lett.. 2012;25:320-325.
[Google Scholar]
Imran M., Baig A.Q., Rashid S., Semaničová-Feňovčíková A., . On the metric dimension and diameter of circulant graphs with three jumps. Discrete Math. Algorithms Appl.. 2018;10(1):1850008.
[Google Scholar]
Imran M., Bokhary S.A.U.H., . On resolvability in double-step circulant graphs, U.P.B. Sci. Bull. Series A. 2014;76(2):31-42.
[Google Scholar]
Javaid I., Azhar M.N., Salman M., . Metric dimension and determining number of Cayley graphs. World Appl. Sci. J.. 2012;18:1800-1812.
[Google Scholar]
Javaid I., Rahim M.T., Ali K., . Families of regular graphs with constant metric dimension. Util. Math.. 2008;75:21-33.
[Google Scholar]
Khuller S., Raghavachari B., Rosenfeld A., . Landmarks in graphs. Discrete Appl. Math.. 1996;70(3):217-229.
[Google Scholar]
Koam A.N.A., Ahmad A., Asim M.A., Azeem M., . Computation of vertex and edge resolvability of benzenoid tripod structure. J. King Saud Univ. Sci.. 2022;34(6):102208.
[Google Scholar]
Melter R.A., Tomescu I., . Metric bases indigital geometry. Comput. Vision Graphics Image Process.. 1984;25:113-121.
[Google Scholar]
Prabhu S., Deepa S., Arulperumjothi M., Susilowati L., Liu J.-B., . Resolving-power domination number of probabilistic neural networks. J. Intell. Fuzzy Syst.. 2022;43(5):6253-6263.
[Google Scholar]
Prabhu S., Manimozhi V., Arulperumjothi M., Klavžar S., . Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks. Appl. Math. Comput.. 2022;420:126897.
[Google Scholar]
Salman M., Javaid I., Chaudhry M.A., . Resolvability in circulant graphs. Acta Math. Sin. (Engl. Ser.). 2012;28(9):1851-1864.
[Google Scholar]
Slater P.J., . Leaves of trees. Congr. Numer.. 1975;14:549-559.
[Google Scholar]
Vetrík T., . On the metric dimension of directed and undirected circulant graphs. Discuss. Math. Graph Theory. 2020;40(1):67-76.
[Google Scholar]
Vetrík T., . The metric dimension of circulant graphs. Canad. Math. Bull.. 2017;60(1):206-216.
[Google Scholar]
Vetrík T., . On the metric dimension of circulant graphs with 4 generators. Contrib. Discrete Math.. 2017;12(2):104-114.
[Google Scholar]

Appendix A

Supplementary material

Supplementary data associated with this article can be found, in the online version, at https://doi.org/10.1016/j.jksus.2023.102834.

Supplementary material

The following are the Supplementary data to this article:

Supplementary data 1

Download

Introduction

New bounds

Concluding remarks and further work

Data availability statement

Author contributions

Fulltext Views
13

PDF downloads
8

View/Download PDF
Download Citations

BibTeX
RIS

Show Sections

[1] Arulperumjothi M., Klavžar S., Prabhu S., . Redefining fractal cubic networks and determining their metric dimension and fault-tolerant metric dimension. Appl. Math. Comput.. 2023;452:128037.
[Google Scholar]

[2] Azeem M., Imran M., Nadeem M.F., . Sharp bounds on partition dimension of hexagonal Möbius ladder. J. King Saud Univ. Sci.. 2022;34(2):101779.
[Google Scholar]

[3] Azhar M.N., Javaid I., . Metric basis in circulant networks. Ars Combin.. 2018;136:277-286.
[Google Scholar]

[4] Borchert A., Gosselin S., . The metric dimension of circulant graphs and Cayley hypergraphs. Util. Math.. 2018;106:125-147.
[Google Scholar]

[5] Chartrand G., Eroh L., Johnson M.A., Oellermann O.R., . Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math.. 2000;105(1–3):99-113.
[Google Scholar]

[6] Chau K., Gosselin S., . The metric dimension of circulant graphs and their Cartesian products. Opuscula Math.. 2017;37(4):509-534.
[Google Scholar]

[7] Du Toit L., Vetrík T., . On the metric dimension of circulant graphs with 2 generators. Kragujevac J. Math.. 2019;43(1):49-58.
[Google Scholar]

[8] Grigorious C., Kalinowski T., Ryan J., Stephen S., . The metric dimension of the circulant graph $C (n, \pm {1, 2, 3, 4})$ . Australas. J. Combin.. 2017;69(3):417-441.
[Google Scholar]

[9] Grigorious C., Manuel P., Miller M., Rajan B., Stephen S., . On the metric dimension of circulant and Harary graphs. Appl. Math. Comput.. 2014;248:47-54.
[Google Scholar]

[10] Imran M., Baig A.Q., Bokhary S.A., Javaid I., . On the metric dimension of circulant graphs. Appl. Math. Lett.. 2012;25:320-325.
[Google Scholar]

[11] Imran M., Baig A.Q., Rashid S., Semaničová-Feňovčíková A., . On the metric dimension and diameter of circulant graphs with three jumps. Discrete Math. Algorithms Appl.. 2018;10(1):1850008.
[Google Scholar]

[12] Imran M., Bokhary S.A.U.H., . On resolvability in double-step circulant graphs, U.P.B. Sci. Bull. Series A. 2014;76(2):31-42.
[Google Scholar]

[13] Javaid I., Azhar M.N., Salman M., . Metric dimension and determining number of Cayley graphs. World Appl. Sci. J.. 2012;18:1800-1812.
[Google Scholar]

[14] Javaid I., Rahim M.T., Ali K., . Families of regular graphs with constant metric dimension. Util. Math.. 2008;75:21-33.
[Google Scholar]

[15] Khuller S., Raghavachari B., Rosenfeld A., . Landmarks in graphs. Discrete Appl. Math.. 1996;70(3):217-229.
[Google Scholar]

[16] Koam A.N.A., Ahmad A., Asim M.A., Azeem M., . Computation of vertex and edge resolvability of benzenoid tripod structure. J. King Saud Univ. Sci.. 2022;34(6):102208.
[Google Scholar]

[17] Melter R.A., Tomescu I., . Metric bases indigital geometry. Comput. Vision Graphics Image Process.. 1984;25:113-121.
[Google Scholar]

[18] Prabhu S., Deepa S., Arulperumjothi M., Susilowati L., Liu J.-B., . Resolving-power domination number of probabilistic neural networks. J. Intell. Fuzzy Syst.. 2022;43(5):6253-6263.
[Google Scholar]

[19] Prabhu S., Manimozhi V., Arulperumjothi M., Klavžar S., . Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks. Appl. Math. Comput.. 2022;420:126897.
[Google Scholar]

[20] Salman M., Javaid I., Chaudhry M.A., . Resolvability in circulant graphs. Acta Math. Sin. (Engl. Ser.). 2012;28(9):1851-1864.
[Google Scholar]

[21] Slater P.J., . Leaves of trees. Congr. Numer.. 1975;14:549-559.
[Google Scholar]

[22] Vetrík T., . On the metric dimension of directed and undirected circulant graphs. Discuss. Math. Graph Theory. 2020;40(1):67-76.
[Google Scholar]

[23] Vetrík T., . The metric dimension of circulant graphs. Canad. Math. Bull.. 2017;60(1):206-216.
[Google Scholar]

[24] Vetrík T., . On the metric dimension of circulant graphs with 4 generators. Contrib. Discrete Math.. 2017;12(2):104-114.
[Google Scholar]

The metric dimension of the circulant graph with 2 k generators can be less than k

Abstract

Keywords

Metric dimension

Resolving set

Distance

Cayley graph

Circulant graph

1 Introduction

2 New bounds

3 Concluding remarks and further work

Data availability statement

Author contributions

Acknowledgements

Declaration of Competing Interest

References

Appendix A

Supplementary material

Supplementary material

Suggested read for related articles:

The metric dimension of the circulant graph with $2 k$ generators can be less than k