nach oben

Journal of Applied Mathematics and Computing

Erschienen in:

21.11.2018 | Original Research

On the fault-tolerant metric dimension of certain interconnection networks

verfasst von: Hassan Raza, Sakander Hayat, Xiang-Feng Pan

Erschienen in: Journal of Applied Mathematics and Computing | Ausgabe 1-2/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Three-step alternating and preconditioned scheme for rectangular matrices

Nächster Artikel Global stability and optimal control for a hepatitis B virus infection model with immune response and drug therapy

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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)\). Miskolc. Math. Notes 16(2), 637–646 (2015)MathSciNetCrossRef

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)MathSciNetCrossRefMATH

Bailey, R.F., Meagher, K.: On the metric dimension of Grassmann graphs. Discrete Math. Theor. Comput. Sci. 13(4), 97–104 (2011)MathSciNetMATH

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)CrossRef

Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)CrossRefMATH

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)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

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)

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)MathSciNetCrossRefMATH

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)CrossRef

11.

Fehr, M., Gosselin, S., Oellermann, O.: The metric dimension of Cayley digraphs. Discrete Math. 306, 31–41 (2006)MathSciNetCrossRefMATH

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)MATH

13.

Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2, 191–195 (1976)MATH

14.

Hayat, S.: Computing distance-based topological descriptors of complex chemical networks: new theoretical techniques. Chem. Phys. Lett. 688, 51–58 (2017)CrossRef

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)

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)MathSciNetCrossRefMATH

18.

Javaid, I., Salman, M., Chaudhry, M.A., Shokat, S.: Fault-tolerance in resolvibility. Utilitas Math. 80, 263–275 (2009)MathSciNetMATH

19.

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

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)MathSciNetMATH

21.

Krishnan, S., Rajan, B.: Fault-tolerant resolvability of certain crystal structures. Appl. Math. 7, 599–604 (2016)CrossRef

22.

Lester, L.N., Sandor, J.: Computer graphics on hexagonal grid. Comput. Graph. 8, 401–409 (1984)CrossRef

23.

Liu, K., Abu-Ghazaleh, N.: Virtual coordinate back tracking for void travarsal in geographic routing. In: Kunz, T., Ravi, S.S. (eds.) Ad-Hoc, Mobile, and Wireless Networks. ADHOC-NOW 2006. Lecture Notes in Computer Science, vol. 4104. Springer, Berlin (2006)

24.

Manuel, P., Rajan, B., Rajasingh, I., Monica, C.: On minimum metric dimension of honeycomb networks. J. Discrete Algorithms 6, 20–27 (2008)MathSciNetCrossRefMATH

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)CrossRef

26.

Parhami, B., Kwai, D.-M.: A unified formulation of honeycomb and diamond networks. IEEE Trans. Parallel Distrib. Syst. 12, 74–79 (2001)CrossRef

27.

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

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

29.

Siddiqui, H.M.A., Imran, M.: Computing the metric dimension of wheel related graphs. Appl. Math. Comput. 242, 624–632 (2014)MathSciNetMATH

30.

Slater, P.J.: Leaves of trees. In: Proceedings of 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer. 549–559 (1975)

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)CrossRef

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)MathSciNetCrossRefMATH

Titel: On the fault-tolerant metric dimension of certain interconnection networks
verfasst von: Hassan Raza
Sakander Hayat
Xiang-Feng Pan
Publikationsdatum: 21.11.2018
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Applied Mathematics and Computing / Ausgabe 1-2/2019
Print ISSN: 1598-5865
Elektronische ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-018-01225-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1-2/2019

M-polynomial revisited: Bethe cacti and an extension of Gutman’s approach

Cyclic codes over )

Transmission dynamics of epidemic spread and outbreak of Ebola in West Africa: fuzzy modeling and simulation

Fuzzy magic labeling of simple graphs

Global stability and optimal control for a hepatitis B virus infection model with immune response and drug therapy

Fractional optimal control of an HIV/AIDS epidemic model with random testing and contact tracing