tailieunhanh - Strong metric dimension: A survey

The strong metric dimension has been a subject of considerable amount of research in recent years. This survey describes the related development by bringing together theoretical results and computational approaches, and places the recent results within their historical and scientific framework. | Yugoslav Journal of Operations Research 24 (2014) Number 2, 187-198 DOI: STRONG METRIC DIMENSION: A SURVEY1 Jozef KRATICA Mathematical Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36, pp. 367, 11 001 Belgrade, Serbia jkratica@ Vera KOVAČEVIĆ-VUJČIĆ, Mirjana ČANGALOVIĆ Faculty of Organizational Sciences, University of Belgrade, Jove Ilića 154, 11 000 Belgrade, Serbia {verakov | canga}@ Nenad MLADENOVIĆ Department of Mathematics, Brunel University, London, UK, Received: Маy 2013 / Accepted: November 2013 Abstract: The strong metric dimension has been a subject of considerable amount of research in recent years. This survey describes the related development by bringing together theoretical results and computational approaches, and places the recent results within their historical and scientific framework. Keywords: Strong metric dimension, graph problems, combinatorial optimization. MSC: 05-02, 05C12, 90C10, 68T20. 1 This research was partially supported by Serbian Ministry of Education, Science and Technological Development under the grants 174010 and 174033. 188 , et al. / Strong Metric Dimension: A Survey 1. INTRODUCTION In this paper we give a survey of the results related to the strong metric dimension of graphs. The strong metric dimension (SMD) is a recently introduced graph invariant [11], connected to well known metric dimension [1,12] that has been widely investigated. Metric dimension of a graph can be defined as follows. Let G be a simple connected undirected graph G = (V, E), where V is a set of vertices, and E is a set of edges. The distance between vertices u and v, . the length of a shortest u-v path is denoted by d(u,v). A vertex x of the graph G resolves two vertices u and v of G if d(x,u) ≠ d(x,v). An ordered vertex set S = {x1, ., xk} is a resolving set of G if for every two distinct vertices of G there exists a vertex of S which .