Fault-tolerant resolvability of some graphs of convex polytopes. (English. Russian original) Zbl 1519.05065
Discrete Math. Appl. 33, No. 3, 177-187 (2023); translation from Diskretn. Mat. 34, No. 4, 108-122 (2022).
Summary: The fault-tolerant resolvability is an extension of metric resolvability in graphs with several intelligent systems applications, for example, network optimization, robot navigation, and sensor networking. The graphs of convex polytopes, which are rotationally symmetric, are essential in intelligent networks due to the uniform rate of data transformation to all nodes. A resolving set is an ordered set \(\mathbb{W}\) of vertices of a connected graph \(G\) in which the vector of distances to the vertices in \(\mathbb{W}\) uniquely determines all the vertices of the graph \(G\). The minimum cardinality of a resolving set of \(G\) is known as the metric dimension of \(G\). If \(\mathbb{W} \setminus \rho\) is also a resolving set for each \(\rho\) in \(\mathbb{W} \). In that case, \( \mathbb{W}\) is said to be a fault-tolerant resolving set. The fault-tolerant metric dimension of \(G\) is the minimum cardinality of such a set \(\mathbb{W} \). The metric dimension and the fault-tolerant metric dimension for three families of convex polytope graphs are studied. Our main results affirm that three families, as mentioned above, have constant fault-tolerant resolvability structures.
MSC:
| 05C12 | Distance in graphs |
| 05C40 | Connectivity |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
Keywords:
convex polytopes; metric dimension; fault-tolerant metric dimension; connected graph; planar graphReferences:
| [1] | Bǎca M., “Labellings of two classes of convex polytopes”, Util. Math., 34 (1988), 24-31. · Zbl 0662.05025 |
| [2] | Basak M., Saha L., Das G. K., Tiwary K., “Fault-tolerant metric dimension of circulant graphs c_n(1, 2, 3)”, Theor. Comput. Sci., 817 (2020), 66-79. · Zbl 1436.05054 |
| [3] | Bashir H., Zahid Z., Kashif A., Zafar S., Liu J. B., “On 2-metric resolvability in rotationally-symmetric graphs”, J. Intell. Fuzzy Syst., 2021, 1-9. |
| [4] | Beerloiva Z., Eberhard F., Erlebach T., Hall A., Hoffmann M., Mihalak M., Ram L., “Network discovery and verification”, IEEE J. Sel. Area Commun., 24 (2006), 2168-2181. |
| [5] | Chartrand G., Eroh L., Johnson M. A., Oellermann O. R., “Resolvability in graphs and the metric dimension of a graph”, Discrete Appl. Math., 105 (2000), 99-113. · Zbl 0958.05042 |
| [6] | Chartrand G., Saenpholphat V., Zhang R., “The independent resolving number of a graph”, Math. Bohem., 128 (2003), 379-393. · Zbl 1050.05043 |
| [7] | Chartrand G., Zhang R., “The theory and applications of resolvability in graphs: a survey”, Congr. Numer., 160 (2003), 47-68. · Zbl 1039.05029 |
| [8] | Chvatal V., “Mastermind”, Combinatorica, 3 (1983), 325-329. · Zbl 0717.05002 |
| [9] | Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979. · Zbl 0411.68039 |
| [10] | Guo X., Faheem M., Zahid Z., Nazeer W., Li J., “Fault-tolerant resolvability in some classes of line graphs”, Math. Probl. in Engineering, 4 (2020), 1-8. · Zbl 1459.05279 |
| [11] | Harary F., Melter R. A., “On the metric dimension of a graph”, Ars Comb., 2 (1976), 191-195. · Zbl 0349.05118 |
| [12] | Hernando C., Mora M., Slater R. J., Wood D. R., “Fault-tolerant metric dimension of graphs”, Ramanujan Math. Soc. Lect. Notes, Proc. Int. Conf. Convexity in Discrete Structures, 5, 2008, 81-85. · Zbl 1170.05306 |
| [13] | Honkala I., Laihonen T., “On locating-dominating sets in infinite grids”, Eur. J. Comb., 27:2 (2006), 218-227. · Zbl 1082.05069 |
| [14] | Javaid I., Salman M., Chaudhry M. A., Shokat S., “Fault-tolerance in resolvability”, Util. Math., 80 (2009), 263-275. · Zbl 1197.05041 |
| [15] | Jesse G., “Metric dimension and pattern avoidance in graphs”, Discret. Appl. Math., 284 (2020), 1-7. · Zbl 1443.05049 |
| [16] | Bensmail J., Inerney F. M., Nisse N., “Metric dimension: from graphs to oriented graphs”, Discret. Appl. Math., 323 (2020), 28-42. · Zbl 1502.05046 |
| [17] | Khuller S., Raghavachari B., Rosenfeld A., “Landmarks in graphs”, Discrete Appl. Math., 70 (1996), 217-229. · Zbl 0865.68090 |
| [18] | Rehman S. ur, Imran M., Javaid I., “On the metric dimension of arithmetic graph of a composite number”, Symmetry, 12:4, #607 (2020), 10 pp. |
| [19] | Raza H., Hayat S., Imran M., Pan X. F., “Fault-tolerant resolvability and extremal structures of graphs”, Mathematics, 7:1, #78 (2019), 19 pp. |
| [20] | Raza H., Hayat S., Pan X. F., “On the fault-tolerant metric dimension of convex polytopes”, Appl. Math. Comput., 339 (2018), 172-185. · Zbl 1428.05085 |
| [21] | Raza H., Hayat S., Pan X. F., “On the fault-tolerant metric dimension of certain interconnection networks”, J. Appl. Math. Comput., 60:1 (2019), 517-535. · Zbl 1417.05053 |
| [22] | Raza H., Liu J. B., Qu S., “On mixed metric dimension of rotationally symmetric graphs”, IEEE Access, 8 (2020), 11560-11569. |
| [23] | Salman M., Javaid I., Chaudhry M. A., Minimum fault-tolerant, local and strong metric dimension of graphs, 2014, 19 pp., arXiv: arXiv:1409.2695 |
| [24] | Sharma S. K., Bhat V. K., “Metric dimension of heptagonal circular ladder”, Discrete Math. Algorithms Appl., 13:1, #2050095 (2021), 17 pp. · Zbl 1459.05067 |
| [25] | Sharma S. K., Bhat V. K., “Fault-tolerant metric dimension of two-fold heptagonal-nonagonal circular ladder”, DiscreteMath. Algorithms Appl., 14:3, #2150132 (2022). · Zbl 1487.05083 |
| [26] | Sharma S. K., Bhat V. K., “On metric dimension of plane graphs 𝔉_n, 𝔎_n, and 𝔏_n”, J. Algebra Comb. Discrete Struct. Appl., 8:3 (2021), 197-212. · Zbl 1482.05071 |
| [27] | Sharma S. K., Bhat V. K., “Edge metric dimension and edge basis of one-heptagonal carbon nanocone networks”, IEEE Access, 10 (2022), 29558-29566. |
| [28] | Siddiqui H. M. A., Hayat S., Khan A., Imran M., Razzaq A., Liu J. -B., “Resolvability and fault-tolerant resolvability structures of convex polytopes”, Theor. Comput. Sci., 796 (2019), 114-128. · Zbl 1433.05104 |
| [29] | Slater P. J., “Leaves of trees”, Congr. Numer., 14 (1975), 549-559. · Zbl 0316.05102 |
| [30] | Soderberg S., Shapiro H. S., “A combinatory detection problem”, Amer. Math. Mon., 70:10 (1963), 1066-1070. · Zbl 0123.00205 |
| [31] | Stojmenovic I., “Direct interconnection networks”, Parallel and Distributed Computing Handbook, eds. Zomaya A. Y., McGraw-Hill, 1996, 537-567. |
| [32] | Xuanlong M., She Y., “The metric dimension of the enhanced power graph of a finite group”, J. Algebra. Appl., 19:1, #2050020 (2020). · Zbl 1437.05098 |
| [33] | Yuezhong Z., Hou L., Hou B., WuW., Du D., Gao S., “On the metric dimension of the folded n-cube”, Optim. Lett., 14:1 (2020), 249-257. · Zbl 1433.05106 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
