On the metric dimension of corona product graphs

Given a set of vertices S = {nu 1, nu 2, ..., vk) of a connected graph C. the metric representation of a vertex u of G with respect to S is the vector r(nu|S) = (d(nu, nu(1)), d(nu, nu(2)), ..., d(nu, nu(k))), where d(nu, nu(i)), i is an element of {1, ..., k) denotes the distance between nu and nu(i). S is a resolving set for G if for every pair of distinct vertices u, nu of G, r(u|S) not equal (nu|S). The metric dimension ofG, dim(G), is the minimum cardinality of any resolving set for G. Let G and H be two graphs of order n(1) and n(2), respectively. The corona product G circle dot H is defined as the graph obtained from G and H by taking one copy of G and n(1) copies of H and joining by an edge each vertex from the ith-copy of H with the ith-vertex of G. For any integer k >= 2, we define the graph G circle dot(k) H recursively from G circle dot H as G circle dot(k) H = (G circle dot(k-1) H) circle dot H. We give several results on the metric dimension of G circle dot(k) H. For instance, we show that given two connected graphs G and H of order n(1) >= 2 and n(2) >= 2, respectively, if the diameter of H is at most two, then dim(G circle dot(k) H) = n(1) (n(2)+ 1)(k-1) dim(H). Moreover, if n(2) >= 7 and the diameter of H is greater than five or H is a cycle graph, then dim(G circle dot H-k) = n(1) (n(2) + 1)(k-1) dim(K-1 circle dot H). (C) 2011 Elsevier Ltd. All rights reserved.