On the Metric Dimension of Cartesian Products of Graphs

Abstract

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.

Cited by in corpus (74)

• On the metric dimension of corona product graphs
• On the strong metric dimension of corona product graphs and join graphs
• A note on the partition dimension of Cartesian product graphs
• Resolving sets for Johnson and Kneser graphs
• On the partition dimension of trees
• On the metric dimension of Cartesian powers of a graph
• Edge metric dimension of some generalized Petersen graphs
• On the local metric dimension of corona product graphs
• The Simultaneous Metric Dimension of Graph Families
• A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs
• Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results
• The connected metric dimension at a vertex of a graph
• The metric dimension of small distance-regular and strongly regular graphs
• Minimum Fault-Tolerant, local and strong metric dimension of graphs
• A Simple Algorithm for Graph Reconstruction
• Broadcast Dimension of Graphs
• On Metric Dimension of Functigraphs
• Sequential metric dimension for random graphs
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
• Approximability of the Minimum Weighted Doubly Resolving Set Problem
• A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
• The resolving number of a graph
• On the power graph of a finite group
• The distance-k dimension of graphs
• On the Metric Dimensions for Sets of Vertices
• On the metric dimension of imprimitive distance-regular graphs
• Resolving sets tolerant to failures in three-dimensional grids
• On the metric dimension of affine planes, biaffine planes and generalized quadrangles
• Is it possible to determine a point lying in a simplex if we know the distances from the vertices?
• Extremal Graph Theory for Metric Dimension and Diameter
• On the Metric Dimension of Infinite Graphs
• The Equidistant Dimension of Graphs
• Metric dimension, minimal doubly resolving sets and the strong metric dimension for jellyfish graph and cocktail party graph
• On the Partition Dimension and the Twin Number of a Graph
• Distance preserving graphs and graph products
• Metric dimension for random graphs
• Minimal resolving sets for the hypercube
• Relations between Metric Dimension and Domination Number of Graphs
• An algorithm for the weighted metric dimension of two-dimensional grids
• Metric Dimension
• Link Dimension and Exact Construction of a Graph
• On the fractional metric dimension of graphs
• On the metric dimension and fractional metric dimension for hierarchical product of graphs
• Metric Dimension of Hamming Graphs and Applications to Computational Biology
• Models for the k-metric dimension
• On the metric dimension of bilinear forms graphs
• Fault Tolerant Metric Dimensions of Leafless Cacti Graphs with Application in Supply Chain Management
• A note on $k$-metric dimensional graphs
• On the metric dimension of line graphs
• Metric dimension of maximal outerplanar graphs
• A characterization of 2-dimensional Cayley graphs on dihedral groups
• The Metric Dimension of The Tensor Product of Cliques
• Extremal Graph Theory for Metric Dimension and Girth
• On the metric dimension, the upper dimension and the resolving number of graphs
• Alliance free sets in Cartesian product graphs
• On Randomly k-Dimensional Graphs
• On minimal doubly resolving sets in graphs
• Metric dimension and edge metric dimension of unicyclic graphs
• Sharp bound on the threshold metric dimension of trees
• Complexity of Metric Dimension on Planar Graphs
• Finite metric and $k$-metric bases on ultrametric spaces
• Completeness-resolvable graphs
• Maker-Breaker resolving game
• Computing Minimal Doubly Resolving Sets and the Strong Metric Dimension of the Layer Sun Graph and the Line Graph of Layer Sun Graph
• Determining sets, resolving sets, and the exchange property
• Neighbor-Locating Colorings in Graphs
• Modular Decomposition of Graphs and the Distance Preserving Property
• On the Broadcast Dimension of a Graph
• Metric dimension of some distance-regular graphs
• Metric dimension of combinatorial game graphs
• Metric dimension of Andrasfai graphs
• Metric Dimension of Amalgamation of Graphs
• Determining sets and determining numbers of finite groups
• The strong metric dimension of the power graph of a finite group