The fault-tolerant metric dimension of the king’s graph

Authors

  • Roman Voronov Petrozavodsk State University, 33, Lenina pr., Petrozavodsk, 185910, Russian Federation

DOI:

https://doi.org/10.21638/11701/spbu10.2017.302

Abstract

The concept of resolving the set within a graph is related to the optimal placement problem of access points in an indoor positioning system. A vertex w of the undirected connected graph G resolves the vertices u and v of G if the distance between vertices w and u differs from the distance between vertices w and v. A subset W of vertices of G is called a resolving set, if every two distinct vertices of G are resolved by some vertex of w ∈ W. The metric dimension of G is a minimum cardinality of its resolving set.The set of access points of the indoor positioning system corresponds to the resolving set of vertices in the graph.The minimum number of access points required to locate each of the vertices corresponds to the metric dimension of graph. A resolving set W of the graph G is fault-tolerant if Wminus{w} is also a resolving set of G, for each w ∈ W. The fault-tolerant metric dimension of the graph G is a minimum cardinality of the fault-tolerant resolving set. In the indoor positioning system the fault-tolerant resolving set provides correct information even when one of the access points is not working. The article describes a special case of a graph called the king’s graph, or the strong product of two paths.The king’s graph is a building model in some indoor positioning systems. In this article we give an upper bound for the fault-tolerant metric of the king’s graph and a formula for a particular case of the king’s graph. Refs 20. Figs 2.

Keywords:

fault-tolerant metric dimension, strong product graphs, king’s graph, access points of indoor positioning system

Downloads

Download data is not yet available.
 

References

Krilatov A. Yu. Optimal’nye strategii upravlenija transportnymi potokami na seti iz parallel’nyh kanalov [Optimal strategies for traffic flow management on the transportation network of parallel links]. Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes, 2014, iss. 2, pp. 120–129. (In Russian)

Raj F. S., George A. On the metric dimension of few network sheets. Robotics, Automation, Control and Embedded Systems — RACE, Intern. conference on robotics. IEEE, 2015, pp. 1–6.

Melter R. A., Tomescu I. Metric bases in digital geometry. Computer Vision, Graphics, and Image Processing, 1984, vol. 25, no. 1, pp. 113–121.

Chaudhry M. A., Javaid I., Salman M. Fault-tolerant metric and partition dimension of graphs. Utilitas Mathematica, 2010, vol. 83, pp. 187–199.

Barragán-Ramírez G. A., Rodríguez-Velázquez J. A. The local metric dimension of strong product graphs. Graphs and Combinatorics, 2016, vol. 32, no. 4, pp. 1263–1278.

Harary F., Melter R. A. On the metric dimension of a graph. Ars Combinatoria, 1976, vol. 2, pp. 191–195.

Slater P. J. Leaves of trees. Proc. 6th Southeastern Conference on Combinatorics, Graph Theory and Computing, 1975, pp. 549–559.

Khuller S., Raghavachari B., Rosenfeld A. Landmarks in graphs. Discrete Applied Mathematics, 1996, vol. 70, no. 3, pp. 217–229.

Chartrand G., Eroh L., Johnson M. A., Oellermann O. R. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 2000, vol. 105, pp. 99–113.

Sebö A., Tannier E. On metric generators of graphs. Mathematics of Operations Research, 2004, vol. 29, no. 2, pp. 383–393.

Fehr M., Gosselin S., Oellermann O. The metric dimension of Cayley digraphs. Discrete Mathematics, 2006, vol. 306, pp. 31–41.

Hernando C., Mora M., Slater P. J., Wood D. R. Fault-tolerant metric dimension of graphs. Proc. Intern. conference Convexity in Discrete Structures, Ramanujan Mathematical Society Lecture Notes, 2008, no. 5, pp. 81–85.

Okamoto F., Phinezy B., Zhang P. The local metric dimension of a graph. Mathematica Bohemica, 2010, vol. 135, no. 3, pp. 239–255.

Bollobas B., Mitsche D., Pralat P. Metric dimension for random graphs. arXiv preprint arXiv:1208.3801, 2012 (Available at: https://arxiv.org/pdf/1208.3801.pdf. (accessed: 1.12.2016).)

Epstein L., Levin A., Woeginger G. J. The (weighted) metric dimension of graphs: hard and easy cases. Algorithmica, 2015, vol. 72, no. 4, pp. 1130–1171.

Imran M. On dimensions of some infinite regular graphs generated by infinite hexagonal grid. Utilitas Mathematica, 2013, vol. 92, pp. 3–15.

Klein D. J., Yi E. A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs. European Journal of Pure and Applied Mathematics, 2012, vol. 5, no. 3, pp. 302–316.

Zejnilović S., Mitsche D., Gomes J., Sinopoli B. Extending the metric dimension to graphs with missing edges. Theoretical Computer Science, 2016, vol. 609, pp. 384–394.

Javaid I., Salman M., Chaudhry M. A., Shokat S. Fault-tolerance in resolvability. Utilitas Mathematica, 2009, vol. 80, pp. 263–275.

Rodríguez-Velázquez J. A., Kuziak D., Yero I. G., Sigarreta J. M. The metric dimension of strong product graphs. Carpathian Journal of Mathematics, 2015, vol. 31, no. 2, pp. 261–268.

Обложка журнала

Downloads

Published

2017-09-12

How to Cite

Voronov, R. (2017). The fault-tolerant metric dimension of the king’s graph. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 13(3), 241–249. https://doi.org/10.21638/11701/spbu10.2017.302

Issue

Vol. 13 No. 3 (2017)

Section

Applied Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.