On the Metric Dimension of Cartesian Products of Graphs

Simple item page
dc.creatorCáceres, José
dc.creatorHernando, Carmen
dc.creatorMora, Mercé
dc.creatorPelayo, Ignacio M.
dc.creatorPuertas, María L.
dc.creatorSeara, Carlos
dc.creatorWood, David R.
dc.date2005-07-26
dc.date2006-03-02
dc.date.accessioned2026-07-07T08:07:07Z
dc.date.available2026-07-07T08:07:07Z
dc.descriptionA 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.
dc.identifierhttps://arxiv.org/abs/math/0507527
dc.identifierhttp://arxiv.org/abs/math/0507527
dc.identifierSIAM J. Discrete Mathematics, 21(2):423-441, 2007
dc.identifierdoi:10.1137/050641867
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/130832
dc.subjectCombinatorics
dc.subject05C12
dc.titleOn the Metric Dimension of Cartesian Products of Graphs
dc.typetext

Files

Collections

arXiv