The connected metric dimension at a vertex of a graph
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 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 z∈S 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):v∈V(G)}. Noting that 1≤dim(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 nonplanar 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.
published proceedings

Theoretical Computer Science
author list (cited authors)

Eroh, L., Kang, C. X., & Yi, E
citation count
complete list of authors

Eroh, LindaKang, Cong XYi, Eunjeong
publication date
publisher
published in
Research
keywords

Connected Metric Dimension

Connected Resolving Set

Distance

Metric Dimension
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume