×

The metric dimension of Cartesian products of graphs. (English) Zbl 1109.05041

Let \(G\) be a connected (di)graph. A vertex \(x\) is said to resolve two vertices \(u\) and \(v\) of \(G\) if the distance from \(u\) to \(x\) does not equal the distance from \(v\) to \(x\). A set \(W\) of vertices of \(G\) is a resolving set of \(G\) if every pair of vertices of \(G\) has a resolving vertex contained in \(W\). The metric dimension \(\dim(G)\) of a graph \(G\) is defined to be the smallest cardinality of a resolving set for \(G\). The authors prove bounds on \(\dim(G\times C)\) where \(C\) is a cycle. Exact values are obtained in the case that \(G\) is also a cycle.

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite