On the fault-tolerant metric dimension of certain interconnection networks. (English) Zbl 1417.05053
Summary: Metric dimension and fault-tolerant metric dimension have potential applications in telecommunication, robot navigation and geographical routing protocols, among others. The computational complexity of these problems is known to be NP-complete. In this paper, we study the fault-tolerant metric dimension of various interconnection networks. By using the resolving sets in these networks, we locate fault-tolerant resolving sets in them. As a result, certain lower and upper bounds on the fault-tolerant metric dimension of those networks are obtained. We conclude the paper with some open problems.
MSC:
| 05C12 | Distance in graphs |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C90 | Applications of graph theory |
Keywords:
metric dimension; fault-tolerant metric dimension; grid networks; hexagonal networks; honeycomb network; hex-derived networksReferences:
| [1] | Ahmad, A., Imran, M., Al-Mushayt, O., Bokhary, S.A.U.H.: On the metric dimension of barycentric subdividion of Cayley graph \[Cay(\mathbb{Z}_n\oplus \mathbb{Z}_m)\] Cay(Zn⊕Zm). Miskolc. Math. Notes 16(2), 637-646 (2015) · Zbl 1349.90789 · doi:10.18514/MMN.2015.1087 |
| [2] | Bailey, R.F., Cameron, P.J.: Basie size, metric dimension and other invariants of groups and graphs. Bull. London Math. Soc. 43, 209-242 (2011) · Zbl 1220.05030 · doi:10.1112/blms/bdq096 |
| [3] | Bailey, R.F., Meagher, K.: On the metric dimension of Grassmann graphs. Discrete Math. Theor. Comput. Sci. 13(4), 97-104 (2011) · Zbl 1286.05035 |
| [4] | Beerloiva, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihalák, M., Ram, L.: Network discovery and verification. IEEE J. Sel. Area Commun. 24, 2168-2181 (2006) · doi:10.1109/JSAC.2006.884015 |
| [5] | Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008) · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5 |
| [6] | Cáceres, J., Hernando, C., Mora, M., Pelayoe, I.M., Puertas, M.L.: On the metric dimension of infinite graphs. Electron. Notes Discrete Math. 35, 15-20 (2009) · Zbl 1268.05140 · doi:10.1016/j.endm.2009.11.004 |
| [7] | Cáceres, J., Hernando, C., Mora, M., Pelayoe, I.M., Puertas, M.L., Seara, C., Wood, D.R.: On the metric dimension of cartesian products of graphs. SIAM J. Discrete Math. 21, 423-441 (2007) · Zbl 1139.05314 · doi:10.1137/050641867 |
| [8] | Chartrand, G., Zhang, P.: The theory and applications of resolvability in graphs: A survey. In: Proceedings of the 34th Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 160, 47-68 (2003) · Zbl 1039.05029 |
| [9] | Chartrand, G., Eroh, L., Johnson, M.A., Oellermann, O.R.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 150, 99-113 (2000) · Zbl 0958.05042 · doi:10.1016/S0166-218X(00)00198-0 |
| [10] | Chen, M.S., Shin, K.G., Kandlur, D.D.: Addressing, routing and broadcasting in hexagonal mesh multiprocessors. IEEE Trans. Comput. 39, 10-18 (1990) · doi:10.1109/12.46277 |
| [11] | Fehr, M., Gosselin, S., Oellermann, O.: The metric dimension of Cayley digraphs. Discrete Math. 306, 31-41 (2006) · Zbl 1085.05034 · doi:10.1016/j.disc.2005.09.015 |
| [12] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979) · Zbl 0411.68039 |
| [13] | Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2, 191-195 (1976) · Zbl 0349.05118 |
| [14] | Hayat, S.: Computing distance-based topological descriptors of complex chemical networks: new theoretical techniques. Chem. Phys. Lett. 688, 51-58 (2017) · doi:10.1016/j.cplett.2017.09.055 |
| [15] | Hayat, S., Malik, M.A., Imran, M.: Computing topological indices of honeycomb derived networks. Rom. J. Inf. Sci. Technol. 18, 144-165 (2015) |
| [16] | Hernando, C., Mora, M., Slater, P.J., Wood, D.R.: Fault-tolerant metric dimension of graphs. In: Proceedings of International Conference on Convexity in Discrete Structures, Ramanujan Mathematical Society Lecture Notes, pp. 81-85. May (2008) · Zbl 1170.05306 |
| [17] | Imran, M., Siddiqui, H.M.A.: Computing the metric dimension of convex polytopes generated by the wheel related graphs. Acta Math. Hung. 149, 10-30 (2016) · Zbl 1389.05029 · doi:10.1007/s10474-016-0606-1 |
| [18] | Javaid, I., Salman, M., Chaudhry, M.A., Shokat, S.: Fault-tolerance in resolvibility. Utilitas Math. 80, 263-275 (2009) · Zbl 1197.05041 |
| [19] | Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Appl. Math. 70, 217-229 (1996) · Zbl 0865.68090 · doi:10.1016/0166-218X(95)00106-2 |
| [20] | Kratica, J., Kovačević-Vujčić, V., Čangalović, M., Stojanović, M.: Minimal doubly resolving sets and the strong metric dimension of some convex polytopes. Appl. Math. Comput. 218, 9790-9801 (2012) · Zbl 1245.90085 |
| [21] | Krishnan, S., Rajan, B.: Fault-tolerant resolvability of certain crystal structures. Appl. Math. 7, 599-604 (2016) · doi:10.4236/am.2016.77055 |
| [22] | Lester, L.N., Sandor, J.: Computer graphics on hexagonal grid. Comput. Graph. 8, 401-409 (1984) · doi:10.1016/0097-8493(84)90038-4 |
| [23] | Liu, K.; Abu-Ghazaleh, N.; Kunz, T. (ed.); Ravi, SS (ed.), Virtual coordinate back tracking for void travarsal in geographic routing, No. 4104 (2006), Berlin |
| [24] | Manuel, P., Rajan, B., Rajasingh, I., Monica, C.: On minimum metric dimension of honeycomb networks. J. Discrete Algorithms 6, 20-27 (2008) · Zbl 1159.05308 · doi:10.1016/j.jda.2006.09.002 |
| [25] | Nocetti, F.G., Stojmenovic, I., Zhang, J.: Addressing and routing in hexagonal networks with applications for tracking mobile users and connection rerouting in cellular networks. IEEE Trans. Parallel Distrib. Syst. 13, 963-971 (2002) · doi:10.1109/TPDS.2002.1036069 |
| [26] | Parhami, B., Kwai, D.-M.: A unified formulation of honeycomb and diamond networks. IEEE Trans. Parallel Distrib. Syst. 12, 74-79 (2001) · doi:10.1109/71.899940 |
| [27] | Raza, H., Hayat, S., Pan, X.-F.: On the fault-tolerant metric dimension of convex polytopes. Appl. Math. Comput. 339, 172-185 (2018) · Zbl 1428.05085 |
| [28] | Salman, M., Javaid, I., Chaudhry, M.A.: Minimum fault-tolerant, local and strong metric dimension of graphs, arXiv preprint arXiv:1409.2695 (2014), http://arxiv.org/pdf/1409.2695 · Zbl 1474.05117 |
| [29] | Siddiqui, H.M.A., Imran, M.: Computing the metric dimension of wheel related graphs. Appl. Math. Comput. 242, 624-632 (2014) · Zbl 1334.05133 |
| [30] | Slater, P.J.: Leaves of trees. In: Proceedings of 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer. 549-559 (1975) · Zbl 0316.05102 |
| [31] | Stojmenovic I.: Direct interconnection networks. In: Zomaya, A.Y. (ed.) Parallel and Distributed Computing Handbook, McGraw-Hill Professional, pp. 537-567 (1996) |
| [32] | Stojmenovic, I.: Honeycomb networks: topological properties and communication algorithms. IEEE Trans. Parallel Distrib. Syst. 8, 1036-1042 (1997) · doi:10.1109/71.629486 |
| [33] | Vetrík, T., Ahmad, A.: Computing the metric dimension of the categorial product of some graphs. Int. J. Comput. Math. 94(2), 363-371 (2015) · Zbl 1362.05042 · doi:10.1080/00207160.2015.1109081 |
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.
