Canadian mathematical bulletin | |
The Metric Dimension of Circulant Graphs | |
Tomáš Vetrik1  | |
[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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201912050577279ZK.pdf | 30KB | download |