On two-dimensional Cayley graphs

Document Type : Research Paper

Authors

1 Department of Mathematics Imam Khomeini International University, P.O, Box 34149-16818 Qazvin, Iran

2 Department of Mathematics, Faculty of sciences, Imam Khomeini International University, Qazvin, Iran

Abstract

A subset W of the vertices of a graph G is a resolving set for G when for each pair of distinct vertices u,v in V (G) there exists w in W such that d(u,w)≠d(v,w). The cardinality of a minimum resolving set for G is the metric dimension of G. This concept has applications in many diverse areas including network discovery, robot navigation, image processing, combinatorial search and optimization. The problem of finding metric dimension is NP-complete for general graphs but the metric dimension of trees can be obtained using a polynomial time algorithm. In this paper, we investigate the metric dimension of Cayley graphs on dihedral groups and we characterize a family of them.
 

Keywords

References

[1] M. Ali, G. Ali, M. Imran, A.Q. Baig, M.K.F. Sha q, On the metric dimension of Mobius ladders, Ars Combin. 105 (2012) 103-410.
[2] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, L.S. Ram, Network dicovery and veri cation, IEEE J. Sel. Areas Commun. 24 (2006) 2168-2181.
[3] A. Behtoei, A. Davoodi, M. Jannesari, B. Omoomi, A characterization of some graphs with metric dimension two, Discrete Math. Algorithm. Appl. (2017) DOI: 10.1142/S1793830917500276.
[4] J. Caceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, D.R. Wood, On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423-441.
[5] V. Chvatal, Mastermind, Combinatorica, 3 (1983) 325-329 .
[6] G. Chartrand, L. Eroh, M.A. Johnson, O.R. Ollermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99-113.
[7] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195.
[8] M. Imran, On the metric dimension of barycentric subdivision of Cayley graphs, Acta Math. Appl. Sin. Engl. Ser. 32 (2016) 1067-1072.
[9] M. Janessari, B. Omoomi, Characterization of n-vertex graphs with metric dimension n-3, Math. Bohem. 139 (2014) 1-23.
[10] A. Kelenc, D. Kuziak, A. Taranenko, I.G. Yero, Mixed metric dimension of graphs, Appl. Math. Comput. 314 (2017) 429-438.
[11] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217-229.
[12] R.A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Gr. Image Process. 25 (1984) 113-121.
[13] M. Salman, I. Javaid, M.A. Chaudhry, Resolvability in circulant graphs, Acta Math. Sin. (Engl. Ser.) 29 (2012) 1851-1864.
[14] A. Sebo, E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383-393.
[15] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549-559.
[16] G. Sudhakara, A.R. Hemanth Kumar, Graphs with metric dimension two-a characterization, World Academy of Science, Engineering and Technology. 36 (2009) 621-626.
Algebraic Structures and Their Applications
Volume 4, Issue 1
February 2017
Pages 43-50

Files

Share

How to cite

Statistics