Fault-tolerant resolvability of double antiprism and its related graphs

Sunny Kumar Sharma, Vijay Kumar Bhat

Abstract


Consider a graph, $\Gamma=(V,E)$, where $V(\Gamma)$ and $E(\Gamma)$ are referred to be its vertex and edge sets respectively. Two vertices $k_{1}$ and $k_{2}$ in $\Gamma$ are said to be resolved by a vertex $k$, if $d(k, k_1)\neq d(k, k_2)$ in $\Gamma$. Then, a subset $R\subseteq V(\Gamma)$ with this property, i.e., every pair of different vertices in $\Gamma$ can be resolved by at least one member of $R$, is said to be a resolving set (RS) for $\Gamma$. The smallest cardinality set $R$ with resolving characteristic is called the metric basis (MB) for $\Gamma$, and the MB set cardinality is the metric dimension (MD) for $\Gamma$, denoted by $dim_{v}(\Gamma)$. A resolving set $R_f$ for $\Gamma$ is said to have the property of fault-tolerance or said to be FTRS (fault-tolerant resolving set) if the property of resolving holds for $R_f-\{k\}$ for every $k$ in $R_f$. The FTMD of $\Gamma$ is the minimum cardinality of a FTRS, denoted $dim_{f}(\Gamma)$. These are also known as the resolvability parameters for the $\Gamma$. We introduce the concept of independence in FTRSs for graphs and derive several results and observations for the same in this manuscript. We also consider three almost similar families of infinite convex polytopes and investigate their FTRSs as well as FTMD.

Full Text:

PDF

References


Z. Ahmad, M. A. Chaudhary, A. Q. Baig, M. A. Zahid, Fault-tolerant metric dimension of P(n, 2) ⊙ K1 graph, J. Discret. Math. Sci. Cryptogr. 24 (2021), no. 2, 647-656.

P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hung. 46 (2003), no. 1, 9–15.

G. Chartrand, V. Saenpholphat, P. Zhang, The independent resolving number of a graph, Math. Bohem. 128 (2003), 379–393.

X. Guo, M. Faheem, Z. Zahid, W. Nazeer, J. Li, Fault-tolerant resolvability in some classes of line graphs, Math. Probl. Eng. 2020, Article ID 1436872.

F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Comb. 2 (1976), 191-195.

J. P. Hayes, A graph model for fault-tolerant computing systems, IEEE Trans Comput. 25 (1976), no. 9, 875–884.

C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Puertas, C. Seara, On the metric dimension of some families of graphs, Electron. Notes Discret. Math. 22 (2005), 129–133.

C. Hernando, M. Mora, P. J. Slater, D. R. Wood, Fault-tolerant metric dimension of graphs, Convexity in discrete structures. 5 (2008), 81-85.

Z. Hussain, M. Munir, A. Ahmad, M. Chaudhary, J. A. Khan, I. Ahmed, Metric basis and metric dimension of 1-pentagonal carbon nanocone networks, Sci. Rep. 10 (2020), no. 1, 19687.

M. Imran, A. Q. Baig, M. K. Shafiq, Classes of convex polytopes with constant metric dimension, Util. Math. 90 (2013), 85-99.

I. Javaid, M. T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21-34.

I. Javaid, M. Salman, M. A. Chaudhry, S. Shokat, Fault-tolerance in resolvability, Util. Math. 80 (2009), 263-275.

S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996), 217-229.

R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Gr. Image Process. 25 (1984), 113-121.

H. Raza, S. Hayat, X.-F.Pan, On the fault-tolerantmetric dimension of convex polytopes, Appl. Math. Comput. 339 (2018), 172–185.

A. Sebo, E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004), no. 2, 383-393.

S. K. Sharma, V. K. Bhat, Metric Dimension of heptagonal circular ladder, Discrete Math. Algorithms Appl. 13 (2021), no. 1, 2050095.

S. K. Sharma, V. K. Bhat, On metric dimension of plane graphs with m/2 number of 10 sided faces, J. Comb. Optim. 44 (2022), no. 3, 1433-1458.

P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549-559.

P. J. Slater, Fault-tolerant locating-dominating sets, Discrete Math. 249 (2002), 179–189.

I. Tomescu, I. Javaid, On the metric dimension of the Jahangir graph, B Math. Soc. Sci Math. 50(98) (2007), 371–376.

R. V. Voronov, The fault-tolerant metric dimension of the king’s graph, Vestnik of Saint Petersburg University. Appl. Math. Comp. Sci. Control Processes. 13 (2017), no. 3, 241–249.

D. B. West, Introduction to graph theory, Upper Saddle River, Prentice Hall, 2001.




DOI: https://doi.org/10.52846/ami.v52i1.1939