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

Roman Voronov

doi:10.21638/11701/spbu10.2017.302

Авторы

Roman Voronov Петрозаводский государственный университет, Российская Федерация, 185910, Петрозаводск, пр. Ленина, 33

DOI:

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

Аннотация

В некотором приближении аналогом задачи оптимального размещения точек доступа системы внутреннего позиционирования служит задача определения метрической размерности графа и построения его разрешающего множества. Пусть вершина w неориентированного связного графа G различает вершины u и v графа G, если расстояние между вершинами w и u отличается от расстояния между вершинами w и v. Подмножество W вершин графа G называется разрешающим, если для каждой пары вершин u и v графа G найдется различающая их вершина w ∈ W. Метрическая размерность графа — это минимальное число вершин в разрешающем подмножестве. Точкам доступа системы внутреннего позиционирования соответствует разрешающее множество вершин графа, а минимально необходимомучислу точек доступа — метрическая размерность графа. Разрешающее множество называется отказоустойчивым, если оно остается разрешающим, даже если из него удалить любую его вершину. Отказоустойчивая метрическая размерность графа — это минимальное число вершин в отказоустойчивом разрешающем подмножестве, что в системе внутреннего позиционирования соответствует возможности определения местоположения объекта даже в случае потери информации от одной из точек доступа. Рассмотрен один частный случай графа — сильное произведение двух простых цепей, называемое иначе графом ходов шахматного короля. Установлена верхняя граница для отказоустойчивой метрической размерности графа ходов короля и приведена формула для одного частного случая. Библиогр. 20 назв. Ил. 2.

Ключевые слова:

отказоустойчивая метрическая размерность, сильное произведение графов, граф ходов короля, точки доступа системы внутреннего позиционирования

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

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.