Characterization of n-Vertex Graphs with Metric Dimension n-3

2011/03/18 by Jannesari, Mohsen, Omoomi, Behnaz · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1103.3588

Abstract

For an ordered set W=\w₁,w₂,...,w_k\ of vertices and a vertex v in a connected graph G, the ordered k-vector r(v|W):=(d(v,w₁),d(v,w₂),...,d(v,w_k)) is called the (metric) representation of v with respect to W, where d(x,y) is the distance between the vertices x and y. The set W is called a resolving set for G if distinct vertices of G have distinct representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension. In this paper, we characterize all graphs of order n with metric dimension n-3.

Cited by

• Metric dimension of Cartesian product of stars

Related

• Metric dimension of lexicographic product of some known graphs
• The Metric Dimension of Lexicographic Product of Graphs
• Metric dimension of some distance-regular graphs
• Metric dimension, doubly resolving set and strong metric dimension for (C_n\Box P_k)\Box P_m
• Metric dimension, minimal doubly resolving sets and the strong metric dimension for jellyfish graph and cocktail party graph