Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Abstract view

The Metric Dimension of Circulant Graphs

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


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 metric dimension, resolving set, circulant graph, Cayley graph, distance
MSC Classifications: 05C35, 05C12 show english descriptions Extremal problems [See also 90C35]
Distance in graphs
05C35 - Extremal problems [See also 90C35]
05C12 - Distance in graphs

© Canadian Mathematical Society, 2018 :