Abstract
In a connected graph G, the distance d(u, v) denotes the distance between two vertices u and v of G. Let W = {w 1, w 2, ···, w k} be an ordered set of vertices of G and let v be a vertex of G. The representation r(v|W) of v with respect to W is the k-tuple (d(v, w 1), d(v,w 2), ···, d(v, w k)). The set W is called a resolving set or a locating set if every vertex of G is uniquely identified by its distances from the vertices of W, or equivalently, if distinct vertices of G have distinct representations with respect to W. A resolving set of minimum cardinality is called a metric basis for G and this cardinality is the metric dimension of G, denoted by β(G). Metric dimension is a generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists). In this paper, we study the metric dimension of barycentric subdivision of Cayley graphs Cay (Z n ⨁ Z 2). We prove that these subdivisions of Cayley graphs have constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of barycentric subdivision of Cayley graphs Cay (Z n ⨁ Z 2).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ali, M., Ali, G., Imran, M., Baig, A.Q., Shafiq, M.K. On the metric dimension of Möbius ladders. Ars Combin., 105: 403–410 (2012)
Buczkowski, P.S., Chartrand, G., Poisson, C., Zhang, P. On k-dimensional graphs and their bases. Periodica Math. Hung., 46(1): 9–15 (2003)
Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M.L., Seara, C., Wood, D.R. On the metric dimension of cartesian product of graphs. SIAM J. Disc. Math., 2(21): 423–441 (2007)
Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O.R. Resolvability in graphs and metric dimension of a graph. Disc. Appl. Math., 105: 99–113 (2000)
Garey, M.R., Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979
Gross, J.L., Yellen, J. Graph theory and its applications. Chapman & Hall/CRC, New York, 2006
Harary, F., Melter, R.A. On the metric dimension of a graph. Ars Combin., 2: 191–195 (1976)
Imran, M., Ahmad, A., Bokhary, S.A., Semaničová-Feňovčíková, A. On classes of regular graphs with constant metric dimension. Acta Math. Scientia, 33: 187–206 (2013)
Imran, M., Baig, A.Q., Ahmad, A. Families of plane graphs with constant metric dimension. Utilitas Math., 88: 43–57 (2012)
Imran, M., Baig, A.Q., Shafiq, M.K., Tomescu, I. On metric dimension of generalized Petersen graphs P(n, 3). Ars Combin., 117: 113–130 (2014)
Imran, M., Bokhary, S.A., Baig, A.Q. On families of convex polytopes with constant metric dimension. Comput. Math. Appl., 60: 2629–2638 (2010)
Imran, M., Baig, A.Q., Bokhary, S.A., Javaid, I. On the metric dimension of circulant graphs. Appl. Math Lett., 25: 320–325 (2012)
Javaid, I., Rahim, M.T., Ali, K. Families of regular graphs with constant metric dimension. Utilitas Math., 75: 21–33 (2008)
Javaid, I., Azhar, M.N., Salman, M. Metric dimension and determining number of Cayley graphs. World Applied Sciences Journal, 18(12): 1800–1812 (2012)
Khuller, S., Raghavachari, B., Rosenfeld, A. Landmarks in graphs. Disc. Appl. Math., 70: 217–229 (1996)
Khuller, S., Raghavachari, B., Rosenfeld, A. Localization in graphs, Technical Report CS-TR-3326, University of Maryland at College Park, 1994
Melter, R.A., Tomescu, I. Metric bases in digital geometry. Computer Vision, Graphics, and Image Processing, 25: 113–121 (1984)
Sebö, A., Tannier, E. On metric generators of graphs. Math. Oper. Res., 29: 383–393 (2004)
Slater, P.J. Leaves of trees. Congress. Numer., 14: 549–559 (1975)
Tomescu, I., Imran, M. On metric and partition dimensions of some infinite regular graphs. Bull. Math. Soc. Sci. Math. Roumanie, 52(100),4???: 461–472 (2009)
Tomescu, I., Javaid, I. On the metric dimension of the Jahangir graph. Bull. Math. Soc. Sci. Math. Roumanie, 50(98), No.4: 371–376 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National University of Sciences and Technology (NUST), H-12, Islamabad, Pakistan.
Rights and permissions
About this article
Cite this article
Imran, M. On the metric dimension of barycentric subdivision of Cayley graphs. Acta Math. Appl. Sin. Engl. Ser. 32, 1067–1072 (2016). https://doi.org/10.1007/s10255-016-0627-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-016-0627-0