Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T15:02:38.586Z Has data issue: false hasContentIssue false

The Metric Dimension of Circulant Graphs

Published online by Cambridge University Press:  20 November 2018

Tomáš Vetrík*
Affiliation:
Department of Mathematics and Applied Mathematics, University of the Free State, Bloemfontein, South Africa e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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\left( G \right)$. The circulant graph ${{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right)$ consists of the vertices ${{v}_{0}},\,{{v}_{1\,}},\,.\,.\,.\,,{{v}_{n\,-\,1}}$ and the edges ${{v}_{i}}{{v}_{i\,+\,j}}$, where $0\,\le \,i\,\le \,n\,-\,1,1\,\le \,j\,\le \,t\,\left( 2\,\le \,t\,\le \,\left\lfloor \frac{n}{2} \right\rfloor \right)$, the indices are taken modulo $n$. Grigorious, Manuel, Miller, Rajan, and Stephen proved that $\dim\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right) \right)\,\ge \,t\,+\,1$ for $t\,<\,\left\lfloor \frac{n}{2} \right\rfloor ,\,n\,\ge \,3$, and they presented a conjecture saying that $\dim\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right) \right)\,=\,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\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,t \right) \right)\,=\,t$. We also prove that $\dim\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right) \right)\,\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$.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 2017

References

[1] Borchert, A. and Gosselin, S., The metric dimension of circulant graphs and Cayley hypergraphs. Util. Math., http://ion.uwinnipeg.ca/-sgosseli/BorchertGosselinposted.pdf.Google Scholar
[2] Grigorious, C., Manuel, P., Miller, M., Rajan, B., and Stephen, S., On the metric dimension of circulant and Harary graphs. Appl. Math. Comput. 248(2014), 47-54. http://dx.doi.Org/10.1016/j.amc.2O14.09.045 Google Scholar
[3] Heydarpour, M. and Maghsoudi, S., The metric dimension of metric manifolds. Bull. Aust. Math. Soc. 91(2015), no. 3, 508513. http://dx.doi.Org/10.1017/S0004972714001129 Google Scholar
[4] Imran, M., Baig, A. Q., Bokhary, S. A., and Javaid, I., On the metric dimension of circulant graphs. Appl. Math. Lett. 25(2012), 320325. http://dx.doi.Org/10.1 01 6/j.aml.2O11.09.008 Google Scholar
[5] Javaid, I., Azhar, M. N., and Salman, M., Metric dimension and determining number of Cayley graphs. World Appl. Sci. J. 18(2012), 18001812.Google Scholar
[6] Jannesari, M. and Omoomi, R., The metric dimension of the lexicographic product of graphs. Discrete Math. 312(2012), no. 22, 33493356. http://dx.doi.Org/10.1016/j.disc.2012.07.025 Google Scholar
[7] Javaid, I., Rahim, M. T., and Ali, K., Families of regular graphs with constant metric dimension. Util. Math. 75(2008), 2133.Google Scholar
[8] Kuziak, D., Yero, I. G., and Rodriguez-Velazquez, J. A., On the strong metric dimension of corona product graphs and join graphs. Discrete Appl. Math. 161(2013), no. 7-8, 10221027. http://dx.doi.Org/10.1016/j.dam.2O12.10.009 Google Scholar
[9] Melter, R. A. and Tomescu, I., Metric bases in digital geometry. Comput. Vision Graphics Image Process. 25(1984), 113121.Google Scholar
[10] Salman, M., Javaid, I., and Chaudhry, M. A., Resolvability in circulant graphs. Acta Math. Sin. (Engl. Ser.) 28(2012), 18511864. http://dx.doi.Org/10.1007/s10114-012-0417-4 Google Scholar
[11] Slater, P. J., Leaves of trees. In: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975) Congr. Numer. 14, Utilitas Math., Winnipeg, MB, 1975, pp. 549559.Google Scholar
[12] Tomescu, I. and Imran, M., On metric and partition dimensions of some infinite regular graphs. Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 52(2009), no. 4, 461472.Google Scholar
[13] Yi, E., The fractional metric dimension of permutation graphs. Acta Math. Sin. (Engl. Ser.) 31(2015), no. 3, 367382. http://dx.doi.Org/!0.1007/s10114-015-4160-5 Google Scholar