Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals → CMB
Abstract view

# The Metric Dimension of Circulant Graphs

Published:2016-08-18
Printed: Mar 2017
• Tomáš Vetrik,
Department of Mathematics and Applied Mathematics , University of the Free State, Bloemfontein, South Africa
 Format: LaTeX MathJax PDF

## Abstract

A subset $W$ of the vertex set of a graph $G$ is called a resolving set of $G$ if for every pair of distinct vertices $u, v$ of $G$, there is $w \in W$ such that the~distance of $w$ and $u$ is different from the distance of $w$ and $v$. The~cardinality of a~smallest resolving set is called the metric dimension of $G$, denoted by $dim(G)$. The circulant graph $C_n (1, 2, \dots , t)$ consists of the vertices $v_0, v_1, \dots , v_{n-1}$ and the~edges $v_i v_{i+j}$, where $0 \le i \le n-1$, $1 \le j \le t$ $(2 \le t \le \lfloor \frac{n}{2} \rfloor)$, the indices are taken modulo $n$. Grigorious et al. [On the metric dimension of circulant and Harary graphs, Applied Mathematics and Computation 248 (2014), 47--54] proved that $dim(C_n (1,2, \dots , t)) \ge t+1$ for $t \lt \lfloor \frac{n}{2} \rfloor$, $n \ge 3$, and they presented a~conjecture saying that $dim(C_n (1,2, \dots , t)) = t+p-1$ for $n=2tk+t+p$, where $3 \le p \le t+1$. We disprove both statements. We show that if $t \ge 4$ is even, there exists an infinite set of values of $n$ such that $dim(C_n (1,2, \dots , t)) = t$. We also prove that $dim(C_n (1,2, \dots , t)) \le t + \frac{p}{2}$ for $n=2tk+t+p$, where $t$ and $p$ are even, $t \ge 4$, $2 \le p \le t$ and $k \ge 1$.
 Keywords: metric dimension, resolving set, circulant graph, Cayley graph, distance
 MSC Classifications: 05C35 - Extremal problems [See also 90C35] 05C12 - Distance in graphs

 top of page | contact us | privacy | site map |

© Canadian Mathematical Society, 2018 : https://cms.math.ca/