On two-dimensional Cayley graphs

Abstract

A subset <em>W </em>of the vertices of a graph <em>G </em>is a resolving set for <em>G </em>when for each pair of distinct vertices <em>u,v in</em><em> </em><em>V </em>(<em>G</em>) there exists <em>w in</em><em> </em><em>W </em>such that <em>d</em>(<em>u,w</em>)≠<em>d</em>(<em>v,w</em>). The cardinality of a minimum resolving set for <em>G </em>is the metric dimension of <em>G.</em> This concept has applications in many diverse areas including network discovery, robot navigation, image processing, combinatorial search and optimization. The problem of finding metric dimension is NP-complete for general graphs but the metric dimension of trees can be obtained using a polynomial time algorithm. In this paper, we investigate the metric dimension of Cayley graphs on dihedral groups and we characterize a family of them.<br />