PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2019 | Vol. 39, no. 3 | 415--423
Tytuł artykułu

Metric dimension of Andrasfai graphs

Treść / Zawartość
Warianty tytułu
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].
Wydawca

Rocznik
Strony
415--423
Opis fizyczny
Bibliogr. 24 poz.
Twórcy
  • Imam Khomeini International University Department of Mathematics, Faculty of Science P.O. Box: 34148-96818, Qazvin, Iran, b.pejman@edu.ikiu.ac.ir
  • Imam Khomeini International University Department of Mathematics, Faculty of Science P.O. Box: 34148-96818, Qazvin, Iran, shpayrovi@ikiu.ac.ir
autor
  • Imam Khomeini International University Department of Mathematics, Faculty of Science P.O. Box: 34148-96818, Qazvin, Iran, a.behtoei@sci.ikiu.ac.ir
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-4eb79e01-47a6-4fc2-8a32-cfddf0da49d1
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.