On the 2-metric resolvability of graphs

Chenggang Huo; Humera Bashir; Zohaib Zahid; Yu Ming Chu; Chenggang Huo; Humera Bashir; Zohaib Zahid; Yu Ming Chu

doi:10.3934/math.2020425

AIMS Mathematics

2020, Volume 5, Issue 6: 6609-6619. doi: 10.3934/math.2020425

Previous Article Next Article

Research article

On the 2-metric resolvability of graphs

1.
School of mathematics and statistics, University of Suzhou, Suzhou 234000, China
2.
Department of Mathematics, University of Management and Technology, Lahore, Pakistan
3.
Department of Mathematics, Huzhou University, Huzhou 313000, P. R. China
4.
Hunan Provincial Key Laboratory of Mathematical Modeling and Analysis in Engineering, Changsha University of Science & Technology, Changsha 410114, P. R. China

Received: 07 July 2020 Accepted: 17 August 2020 Published: 25 August 2020
MSC : 68R01, 68R05, 68R10

Let $G = (V(G), E(G))$ be a graph. An ordered set of vertices $\Re = \{v_1, v_2, \ldots, v_l\}$ is a $2-$resolving set for $G$ if for any distinct vertices $s, w \in V(G)$, the representation of vertices $r(s|\Re) = (d_G(s, v_1), \ldots, d_G(s, v_l))$ and $r(w|\Re) = (d_G(w, v_1), \ldots, d_G(w, v_l))$ differs in at least $2$ positions. A $2-$resolving set of minimum cardinality is called a $2-$metric basis of $G$ and its cardinality is called the $2-$metric dimension (fault-tolerant metric dimension). In this article, the exact value of the $2-$metric dimension of the family circulant graph $C_n(1, 2)$ is computed and thereby disproving the conjecture given by H. Raza et al., [Mathematics. 2019, 7(1), 78]. The $2-$metric dimension of the family generalized prism graph $P_m\times C_n$ and the Möbius ladder graph $M_n$ is computed. Furthermore, we improved the result given by M. Ali et al., [Ars Combinatoria 2012,105,403-410].
- $k-$metric dimension,
- circulant graph,
- the generalized prism graph,
- Möbius ladder
Citation: Chenggang Huo, Humera Bashir, Zohaib Zahid, Yu Ming Chu. On the 2-metric resolvability of graphs[J]. AIMS Mathematics, 2020, 5(6): 6609-6619. doi: 10.3934/math.2020425

Related Papers:

Abstract

Let $G = (V(G), E(G))$ be a graph. An ordered set of vertices $\Re = \{v_1, v_2, \ldots, v_l\}$ is a $2-$resolving set for $G$ if for any distinct vertices $s, w \in V(G)$, the representation of vertices $r(s|\Re) = (d_G(s, v_1), \ldots, d_G(s, v_l))$ and $r(w|\Re) = (d_G(w, v_1), \ldots, d_G(w, v_l))$ differs in at least $2$ positions. A $2-$resolving set of minimum cardinality is called a $2-$metric basis of $G$ and its cardinality is called the $2-$metric dimension (fault-tolerant metric dimension). In this article, the exact value of the $2-$metric dimension of the family circulant graph $C_n(1, 2)$ is computed and thereby disproving the conjecture given by H. Raza et al., [Mathematics. 2019, 7(1), 78]. The $2-$metric dimension of the family generalized prism graph $P_m\times C_n$ and the Möbius ladder graph $M_n$ is computed. Furthermore, we improved the result given by M. Ali et al., [Ars Combinatoria 2012,105,403-410].

References

[1]	H. Raza, S. Hayat, M. Imran, et al., Fault-Tolerant resolvability and extremal structures of graphs, Mathematics, 7 (2019), 78.
[2]	M. Ali, G. Ali, M. Imran, et al., On the metric dimension of mobius ladders, Ars Combinatoria, 105 (2012), 403-410.
[3]	X. Guo, Y. M. Chu, M. K. Hashmi, et al., Irregularity Measures for Metal-Organic Networks, Math. Probl. Eng., 2020.
[4]	X. Ma, M. A. Umar, S. Nazeer, et al., Stacked book graphs are cycle-antimagic, AIMS Mathematics, 5 (2020), 6043.
[5]	A. Ali, W. Nazeer, M. Munir, et al. M-polynomials and topological indices of zigzag and rhombic benzenoid systems, Open Chemistry, 16 (2018), 73-78. doi: 10.1515/chem-2018-0010
[6]	W. Gao, M. Asif, W. Nazeer, The study of honey comb derived network via topological indices, Open J. Math. Anal., 2 (2018), 10-26.
[7]	W. Gao, A. Asghar, W. Nazeer, Computing degree-based topological indices of Jahangir graph, Engineering and Applied Science Letters, 1 (2018), 16-22.
[8]	S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Disc. Appl. Math., 70 (1996), 217-229. doi: 10.1016/0166-218X(95)00106-2
[9]	L. M. Blumenthal, Theory and applications of distance geometry, Oxford University Press, 1953.
[10]	P. J. Slater, Dominating and referece set in a graph, Journal of Mathematical and Physical Sciences, 22 (1988), 445-455.
[11]	P. J. Slater, Leaves of trees, Congressus Numerantium, 14 (1975), 549-559.
[12]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191-195.
[13]	G. Chartrand and P. Zhang, The theory and applications of resolvability in graphs, A Survey. Congressus Numerantium, 160 (2003), 47-68.
[14]	A. Estrado-Moreno, J. A. Rodriguez-Velaquez and I. G. Yero, The k-metric dimension of a graph, Appl. Math. Inform. Sci., 9 (2015), 2829-2840.
[15]	A. Estrado-Moreno, I. G. Yero and J. A. Rodriguez-Velaquez, Computing the k-metric dimension of graph, Appl. Math. Comput., 300 (2017), 60-69.
[16]	R. F. Bailey and I. G. Yero, Error correcting codes from k-resolving sets, Discussiones Mathematicae, 392 (2019), 341-345.
[17]	A. Estrado-Moreno, I. G. Yero and J. A. Rodriguez-Velaquez, k-metric resolvability in graphs, Electron Notes Discrete Math., 46 (2014), 121-128. doi: 10.1016/j.endm.2014.08.017
[18]	A. Estrado-Moreno, I. G. Yero and J. A. Rodriguez-Velaquez, On the k-metric dimension of metric spaces, arXiv:1603.04049v1, 2016.
[19]	A. Estrado-Moreno, I. G. Yero and J. A. Rodriguez-Velaquez, The k-metric dimension of corona product of graphs, Bull. Malays. Math. Sci. Soc., 39 (2016), 135-156. doi: 10.1007/s40840-015-0282-2
[20]	A. Estrado-Moreno, I. G. Yero and J. A. Rodriguez-Velaquez, The k-metric dimension of lexicographic product of graphs, Discrete Mathematics, 339 (2016), 1924-1934. doi: 10.1016/j.disc.2015.12.024
[21]	A. Estrado-Moreno, I. G. Yero and J. A. Rodriguez-Velaquez, The k-metric dimension of graphs: a general approach, arXiv:1605.06709v2, 2016.
[22]	P. J. Slater, Fault-tolerant locating dominant set, Discrete Math., 219 (2002), 179-189.
[23]	C. Hernando, M. Mora, P. J. Slater, et al. Fault-tolerant metric dimension of graphs, Convexity in discrete structures, 5 (2008), 81-85.
[24]	B. Humera, Z. Zahid, T. Rashid, Computation of 2-metric dimension of some families of graphs, Submitted.
[25]	Z. Ahmad, M. O. Ahmad, A. Q. Baig, et al. Fault-tolerant metric dimension of P(n, 2) with prism graph, arXiv:1811.05973 [math.CO].
[26]	M. Basak, L. Saha, G. K. Das, et al. Fault-tolerant metric dimension of circulant graphs C_n(1, 2, 3), Theoret. Comput. Sci., 2019.
[27]	M. A. Chaudhry, I. Javaid and M. Salman, Fault-tolerant metric and partition dimension of graphs, Util. Math., 83 (2010), 187-199.
[28]	A. Estrado-Moreno, I. G. Yero and J. A. Rodriguez-Velaquez, Relationship between the 2-metric dimension and the 2-adjacency dimension in the lexicographic product of graphs, Graphs and Combinatorics, 32 (2016), 2367-2392. doi: 10.1007/s00373-016-1736-5
[29]	I. Javaid, M. Salman, M. A. Chaudhry, et al. Fault-Tolerance in resolvability, Utilitas Math., 80 (2009), 263-275.
[30]	J. B. Liu, M. Munir, I. Ali, et al. Fault-Tolerant Metric Dimension of Wheel related Graphs, hal-01857316v2, 2019.
[31]	H. Raza, S. Hayat and X. Pan, On the fault-Tolerant metric dimension of convex polytopes, Appl. Math. Comput., 339 (2018), 172-185.
[32]	A. Shabbir and T. Zumfererscu, Fault-tolerant designs in triangular lattice network, Discrete Math., 219 (2002), 179-189.
[33]	A. Borchert and S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, Util. Math., 106 (2018), 125-147.
[34]	I. Javaid, M. T. Rahim and K. Ali, Families of regular graphs with constant metric dimension, Utilitas Math., 75 (2008), 21-33.

Reader Comments

Your name:*

Email:*
© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)