Computing the metric dimension of kayak paddles graph and cycles with chord

• Ahmad, Ali ^[1] ; Bača, Martin ^[2] ; Sultan, Saba ^[3]
  1. [1] Jazan University

     Jazan University

     Arabia Saudí

     
  2. [2] Technical University.
  3. [3] Government College University.

  Mostrar afiliaciones +
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 39, Nº. 2, 2020, págs. 287-300
• Idioma: inglés
• DOI: 10.22199/issn.0717-6279-2020-02-0018
• Enlaces
  • Texto completo
• Resumen

  • A set of vertices W is a resolving set of a graph G if every two vertices of G have distinct representations of distances with respect to the set W. The number of vertices in a smallest resolving set is called the metric dimension. This invariant has extensive applications in robotics, since the metric dimension can represent the mínimum number of landmarks, which uniquely determine the position of a robot moving in a graph space. Finding the metric dimension of a graph is an NP-hard problem. We present exact values of the metric dimensión of Kayak Paddles graph and Cycles with chord.

• Referencias bibliográficas
  • M. Ali, G. Ali, A. Q. Baig, and M. K. Shafiq, “On the metric dimension of Möbius ladders”, Ars combinatoria, vol. 105, pp. 403-410, Jul. 2012.
  • M. Ali, G. Ali, U. Ali, and M. T. Rahim, “On cycle related graphs with constant metric dimension”, Open journal of discrete mathematics, vol....
  • M. Bača, E. T. Baskoro, A. N. M. Salman, S. W. Saputro, and D.Suprijanto, “The metric dimension of regular bipartite graphs”, Bulletin mathématique...
  • C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Cáceres, and M. L. Puertas, “On the metric dimension of some families of graphs”, Electronic...
  • J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, and D. R. Wood, “On the metric dimension of cartesian products of...
  • M. Fehr, S. Gosselin, and O. R. Oellermann, “The metric dimension of Cayley digraphs”, Discrete mathematics, vol. 306, no. 1, pp. 31–41, Jan....
  • M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP - completeness. San Francisco , CA: W.H. Freeman...
  • F. Harary and R. A. Melter, “On the metric dimension of a graph”, Ars combinatoria, vol. 2, pp. 191-195, 1976.
  • M. Imran, A. Q. Baig, and A. Ahmad, “Families of plane graphs with constant metric dimensión”, Utilitas mathematica, in press.
  • M. Imran, A. Q. Baig, M. K. Shafiq and A. Semeničová, “Classes of convex polytopes with constant metric dimensión”, Utilitas mathematica,...
  • M. Imran, S. A. Bokhary, and A. Q. Baig, “On families of convex polytopes with constant metric dimension”, Computers & mathematics with...
  • M. Imran and A. Q. Baig, “A special class of convex polytopes with constant metric dimension”, Journal of combinatorial mathematics and combinatorial...
  • M. Imran and A. Q. Baig, “An infinite class of polytopes with constant metric dimension”, Journal of combinatorial mathematics and combinatorial...
  • M. Imran, A. Baig, S. A. Bokhary, and I. Javaid, “On the metric dimension of circulant graphs”, Applied mathematics letters, vol. 25, no....
  • M. Imran, A. Q. Baig, S. A. Bokhary, and E.T. Baskoro, “New classes of convex polytopes with constant metric dimension”, Utilitas mathematica,...
  • H. Iswadi, E. T. Baskoro, and R. Simanjuntak, “On the metric dimension of corona product of graphs”, Far east journal of mathematical sciences,...
  • M. Jannesari and B. Omoomi, “The metric dimension of the lexicographic product of graphs”, Discrete mathematics, vol. 312, no. 22, pp. 3349–3356,...
  • I. Javaid, M. T. Rahim, and K. Ali, “Families of regular graphs with constant metric dimensión”, Utilitas mathematica, vol. 75, pp. 21-33,...
  • S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs”, Discrete applied mathematics, vol. 70, no. 3, pp. 217–229, Oct. 1996,...
  • R. A. Melter and I. Tomescu, “Metric bases in digital geometry”, Computer vision, graphics, and image processing, vol. 25, no. 1, pp. 113–121,...
  • R. Naeem and M. Imran, “Metric dimension and exchange property for resolving sets in rotationally-symmetric graphs”, Applied Mathematics &...
  • S. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. Baskoro, A. Salman, and M. Bača, “The metric dimension of the lexicographic...
  • H. M. A. Siddiqui and M. Imran, “Computation of metric dimension and partition dimension of nanotubes”, Journal of computational and theoretical...
  • P. J. Slater, “Dominating and reference sets in graphs”, Journal of mathematical and physical sciences, vol. 22, n. 4. pp. 445-455, 1998.
  • P. J. Slater, “Leaves of tres”, Congressus numerantium, vol. 14, pp. 549-559, 1975.
  • C. Poisson and P. Zhang, “The metric dimension of unicyclic graphs”, Journal of combinatorial mathematics and combinatorial computing, vol....
  • I. Tomescu and I. Javaid, “On the metric dimension of Jahangir graph”, Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie,...