The Metric Dimension of Circulant Graphs

Vetrík, Tomáš

Canadian mathematical bulletin, Tome 60 (2017) no. 1, pp. 206-216

Résumé

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$ .

Détail

DOI : 10.4153/CMB-2016-048-1

Mots-clés : 05C35, 05C12, metric dimension, resolving set, circulant graph, Cayley graph, distance

Bibliographie

[1] [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] [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] [3] Heydarpour, M. and Maghsoudi, S., The metric dimension of metric manifolds. Bull. Aust. Math. Soc. 91(2015), no. 3, 508–513. http://dx.doi.Org/10.1017/S0004972714001129 Google Scholar

[4] [4] Imran, M., Baig, A. Q., Bokhary, S. A., and Javaid, I., On the metric dimension of circulant graphs. Appl. Math. Lett. 25(2012), 320–325. http://dx.doi.Org/10.1 01 6/j.aml.2O11.09.008 Google Scholar

[5] [5] Javaid, I., Azhar, M. N., and Salman, M., Metric dimension and determining number of Cayley graphs. World Appl. Sci. J. 18(2012), 1800–1812. Google Scholar

[6] [6] Jannesari, M. and Omoomi, R., The metric dimension of the lexicographic product of graphs. Discrete Math. 312(2012), no. 22, 3349–3356. http://dx.doi.Org/10.1016/j.disc.2012.07.025 Google Scholar

[7] [7] Javaid, I., Rahim, M. T., and Ali, K., Families of regular graphs with constant metric dimension. Util. Math. 75(2008), 21–33. Google Scholar

[8] [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, 1022–1027. http://dx.doi.Org/10.1016/j.dam.2O12.10.009 Google Scholar

[9] [9] Melter, R. A. and Tomescu, I., Metric bases in digital geometry. Comput. Vision Graphics Image Process. 25(1984), 113–121. Google Scholar

[10] [10] Salman, M., Javaid, I., and Chaudhry, M. A., Resolvability in circulant graphs. Acta Math. Sin. (Engl. Ser.) 28(2012), 1851–1864. http://dx.doi.Org/10.1007/s10114-012-0417-4 Google Scholar

[11] [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. 549–559. Google Scholar

[12] [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, 461–472. Google Scholar

[13] [13] Yi, E., The fractional metric dimension of permutation graphs. Acta Math. Sin. (Engl. Ser.) 31(2015), no. 3, 367–382. http://dx.doi.Org/!0.1007/s10114-015-4160-5 Google Scholar