Opuscula Math. 39, no. 3 (2019), 415-423
https://doi.org/10.7494/OpMath.2019.39.3.415

Opuscula Mathematica

# Metric dimension of Andrásfai graphs

S. Batool Pejman
Shiroyeh Payrovi
Ali Behtoei

Abstract. A set $$W\subseteq V(G)$$ is called a resolving set, if for each pair of distinct vertices $$u,v\in V(G)$$ there exists $$t\in W$$ such that $$d(u,t)\neq d(v,t)$$, where $$d(x,y)$$ is the distance between vertices $$x$$ and $$y$$. The cardinality of a minimum resolving set for $$G$$ is called the metric dimension of $$G$$ and is denoted by $$\dim_M(G)$$. This parameter has many applications in different areas. The problem of finding metric dimension is NP-complete for general graphs but it is determined for trees and some other important families of graphs. In this paper, we determine the exact value of the metric dimension of Andrásfai graphs, their complements and $$And(k)\square P_n$$. Also, we provide upper and lower bounds for $$dim_M(And(k)\square C_n)$$.

Keywords: resolving set, metric dimension, Andrásfai graph, Cayley graph, Cartesian product.

Mathematics Subject Classification: 05C12, 05C25.

Full text (pdf)

1. R.F. Bailey, P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. London Math. Soc. 43 (2011), 209-242.
2. Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalák, L.S. Ram, Network discovery and verification, 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. 09 (2017), 1-15.
4. A. Behtoei, Y. Golkhandy Pour, On two-dimensional Cayley graphs, Alg. Struc. Appl. 4 (2017) 1, 43-50.
5. B. Bollobás, Metric dimension for random graphs, Electron. J. Combin. 20 (2013), 1-19.
6. 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.
7. 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.
8. K. Chau, S. Gosselin, The metric dimension of circulant graphs and their cartesian products, Opuscula Math. 37 (2017), 509-534.
9. V. Chvátal, Mastermind, Combinatorica 3 (1983),325-329.
10. M. Fehr, S. Gosselin, O.R. Oellermann, The metric dimension of Cayley digraphs, Discrete Math. 306 (2006), 31-41.
11. G. Fijavž, B. Mohar, Rigidity and separation indices of Paley graphs, Discrete Math. 289 (2004), 157-161.
12. F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195.
13. M. Imran, On the metric dimension of barycentric subdivision of Cayley graphs, Acta Math. Appl. Sin. Engl. Ser. 32 (2016), 1067-1072.
14. M. Janessari, B. Omoomi, Characterization of $$n$$-vertex graphs with metric dimension $$n-3$$, Math. Bohem. 139 (2014), 1-23.
15. S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996), 217-229.
16. R.A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Gr. Image Process. 25 (1984), 113-121.
17. O.R. Oellermann, C.D. Pawluck, A. Stokke, The metric dimension of Cayley digraphs of abelian groups, Ars Comb. 81 (2006), 97-111.
18. J. Peters-Franser, O.R. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006), 33-41.
19. R. Rosiek, M. Woźniak, A note introducing Cayley graphs and group-coset graphs generated by graph packings, Opuscula Math. 24 (2004), 203-221.
20. M. Salman, I. Javaid, M.A. Chaudhry, Resolvability in circulant graphs, Acta Math. Sin. (Engl. Ser.) 29 (2012), 1851-1864.
21. A. Sebo, E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004), 383-393.
22. P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549-559.
23. G. Sudhakara, A.R. Hemanth Kumar, Graphs with metric dimension two - A characterization, World Academy of Science, Engineering and Technology 36 (2009), 621-626.
24. E. Vatandoost, A. Behtoei, Y. Golkhandy Pour, Cayley graphs with metric dimension two - A characterization, https://arxiv.org/abs/1609.06565.
• Communicated by Andrzej Żak.
• Revised: 2018-08-19.
• Accepted: 2018-08-21.
• Published online: 2019-02-23.