The Metric Dimension of Circulant Graphs

Canadian mathematical bulletin

Tomáš Vetrik¹ 

[1] Department of Mathematics and Applied Mathematics , University of the Free State, Bloemfontein, South Africa

关键词: metric dimension;    resolving set;    circulant graph;    Cayley graph;    distance;   

DOI  :  10.4153/CMB-2016-048-1

学科分类：数学（综合）

来源: University of Toronto Press * Journals Division

【 摘 要 】

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} floor)$, 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} floor$, $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$.

【 授权许可】

Unknown