On the Metric Dimension of Cartesian Products of Graphs

Details On the Metric Dimension of Cartesian Products of Graphs On the Metric Dimension of Cartesian Products of Graphs

2005-07-26

arxiv.org/abs/math/0507527v3

SIAM J. Discrete Mathematics, 21(2):423-441, 2007

Mathematics

Combinatorics

Scientific paper

10.1137/050641867

A set S of vertices in a graph G resolves G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. This paper studies the metric dimension of cartesian products G*H. We prove that the metric dimension of G*G is tied in a strong sense to the minimum order of a so-called doubly resolving set in G. Using bounds on the order of doubly resolving sets, we establish bounds on G*H for many examples of G and H. One of our main results is a family of graphs G with bounded metric dimension for which the metric dimension of G*G is unbounded.

Affiliated with

Also associated with

No associations

Rating

On the Metric Dimension of Cartesian Products of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Metric Dimension of Cartesian Products of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Metric Dimension of Cartesian Products of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-208852