Computing the metric dimension of kayak paddles graph and cycles with chord
DOI:
https://doi.org/10.22199/issn.0717-6279-2020-02-0018Keywords:
Metric dimension, Resolving set, Kayak paddles, RoboticsAbstract
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.
References
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. 02, no. 01, pp. 21–23, 2012, doi: 10.4236/ojdm.2012.21005.
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 de la Société des Sciences Mathématiques de Roumanie, vol. 54, no. 1, pp. 15-28, 2011. [On line]. Available: https://bit.ly/2S12YpQ
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 notes in discrete mathematics, vol. 22, pp. 129–133, Oct. 2005, doi: 10.1016/j.endm.2005.06.023.
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 graphs”, SIAM journal on discrete mathematics, vol. 21, no. 2, pp. 423–441, 2007., doi:10.1137/050641867.
M. Fehr, S. Gosselin, and O. R. Oellermann, “The metric dimension of Cayley digraphs”, Discrete mathematics, vol. 306, no. 1, pp. 31–41, Jan. 2006, doi: 10.1016/j.disc.2005.09.015.
M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP - completeness. San Francisco , CA: W.H. Freeman and Co., 1979.
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, in press.
M. Imran, S. A. Bokhary, and A. Q. Baig, “On families of convex polytopes with constant metric dimension”, Computers & mathematics with applications, vol. 60, no. 9, pp. 2629–2638, Nov. 2010, doi: 10.1016/j.camwa.2010.08.090
M. Imran and A. Q. Baig, “A special class of convex polytopes with constant metric dimension”, Journal of combinatorial mathematics and combinatorial computing, vol. 77, pp. 197-205, May 2011.
M. Imran and A. Q. Baig, “An infinite class of polytopes with constant metric dimension”, Journal of combinatorial mathematics and combinatorial computing, in press.
M. Imran, A. Baig, S. A. Bokhary, and I. Javaid, “On the metric dimension of circulant graphs”, Applied mathematics letters, vol. 25, no. 3, pp. 320–325, Mar. 2012, doi: 10.1016/j.aml.2011.09.008.
M. Imran, A. Q. Baig, S. A. Bokhary, and E.T. Baskoro, “New classes of convex polytopes with constant metric dimension”, Utilitas mathematica, in press.
H. Iswadi, E. T. Baskoro, and R. Simanjuntak, “On the metric dimension of corona product of graphs”, Far east journal of mathematical sciences, vol. 52, no. 2, pp. 155-170, May 2011. [On line]. Available: https://bit.ly/3bCnuF2
M. Jannesari and B. Omoomi, “The metric dimension of the lexicographic product of graphs”, Discrete mathematics, vol. 312, no. 22, pp. 3349–3356, Nov. 2012, doi: 10.1016/j.disc.2012.07.025.
I. Javaid, M. T. Rahim, and K. Ali, “Families of regular graphs with constant metric dimensión”, Utilitas mathematica, vol. 75, pp. 21-33, 2008.
S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs”, Discrete applied mathematics, vol. 70, no. 3, pp. 217–229, Oct. 1996, doi: 10.1016/0166-218x(95)00106-2.
R. A. Melter and I. Tomescu, “Metric bases in digital geometry”, Computer vision, graphics, and image processing, vol. 25, no. 1, pp. 113–121, Jan. 1984, doi: 10.1016/0734-189X(84)90051-3.
R. Naeem and M. Imran, “Metric dimension and exchange property for resolving sets in rotationally-symmetric graphs”, Applied Mathematics & Information Sciences, vol. 8, no. 4, pp. 1665–1674, Jul. 2014, doi: 10.12785/amis/080422.
S. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. Baskoro, A. Salman, and M. Bača, “The metric dimension of the lexicographic product of graphs”, Discrete mathematics, vol. 313, no. 9, pp. 1045–1051, May 2013, doi: 10.1016/j.disc.2013.01.021.
H. M. A. Siddiqui and M. Imran, “Computation of metric dimension and partition dimension of nanotubes”, Journal of computational and theoretical nanoscience, vol. 12, no. 2, pp. 199–203, Feb. 2015, doi: 10.1166/jctn.2015.3717
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. 40, pp. 17-32, 2002.
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, vol. 50, no. 4, pp. 371-376, 2007. [On line]. Available: https://bit.ly/2VVx4Mq
Published
How to Cite
Issue
Section
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
