Metric dimension of Andrasfai graphs

• Autorzy: Pejman S. Batool , Payrovi Shiroyeh , Behtoei Ali

Identyfikatory

DOI

10.7494/OpMath.2019.39.3.415

• Języki publikacji: EN

Abstrakty

EN

A set W ⊆ V(G) is called a resolving set, if for each pair of distinct vertices u,v ∈ V(G) there exists t ∈ W such that d(u,t) ≠ 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 dimM(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 Andrasfai graphs, their complements and [formula]. Also, we provide upper and lower bounds for [formula].

Słowa kluczowe

EN

resolving set; metric dimension; Andrasfai graph; Cayley graph; Cartesian product

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2019
• Tom: Vol. 39, no. 3
• Strony: 415--423
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Pejman S. Batool

• Imam Khomeini International University Department of Mathematics, Faculty of Science P.O. Box: 34148-96818, Qazvin, Iran

autor

Payrovi Shiroyeh

• Imam Khomeini International University Department of Mathematics, Faculty of Science P.O. Box: 34148-96818, Qazvin, Iran

autor

Behtoei Ali

• Imam Khomeini International University Department of Mathematics, Faculty of Science P.O. Box: 34148-96818, Qazvin, Iran

Bibliografia

• [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. Mihalak, 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. Struć. Appl. 4 (2017) 1, 43-50.
• [5] B. Bollobas, 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. Chvatal, 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. Fijavz, 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.