The connected metric dimension at a vertex of a graph
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2018 Elsevier B.V. The notion of metric dimension, dim(G), of a graph G, as well as a number of variants, is now well studied. In this paper, we begin a local analysis of this notion by introducing cdimG(v), the connected metric dimension of G at a vertex v, which is defined as follows: a set of vertices S of G is a resolving set if, for any pair of distinct vertices x and y of G, there is a vertex zS such that the distance between z and x is distinct from the distance between z and y in G. We say that a resolving set S is connected if S induces a connected subgraph of G. Then, cdimG(v) is defined to be the minimum of the cardinalities of all connected resolving sets which contain the vertex v. The connected metric dimension of G, denoted by cdim(G), is min{cdimG(v):vV(G)}. Noting that 1dim(G)cdim(G)cdimG(v)|V(G)|1 for any vertex v of G, we show the existence of a pair (G,v) such that cdimG(v) takes all positive integer values from dim(G) to |V(G)|1, as v varies in a fixed graph G. We characterize graphs G and their vertices v satisfying cdimG(v){1,|V(G)|1}. We show that cdim(G)=2 implies G is planar, whereas it is well known that there is a non-planar graph H with dim(H)=2. We also characterize trees and unicyclic graphs G satisfying cdim(G)=dim(G). We show that cdim(G)dim(G) can be arbitrarily large. We determine cdim(G) and cdimG(v) for some classes of graphs. We further examine the effect of vertex or edge deletion on the connected metric dimension. We conclude with some open problems.
