The partition dimension of corona product graphs
Juan Alberto Rodriguez-Velazquez, Ismael G. Yero, Dorota Kuziak · Ars Combinatoria · 2016
Given a set of vertices S = {ν1,ν2, -,νk} of a connected graph G, the metric representation of a vertex ν of G with respect to S is the vector r(ν|5) = (d(ν, ν1),d(ν, ν2),···,d(ν, νk)), where d(ν,νi), i ∈ {1,···,k} denotes the distance between ν and νi. S is a resolving set of G if for every pair of distinct vertices u, ν of G, r(u|S) ¢ r (ν|S). The metric dimension dim(G) of G is the minimum cardinality of any resolving set of G. Given an ordered partition II = {P1,P2,···,Pt} of vertices of a connected graph G, the partition representation of a vertex ν of G, with respect to the partition II is the vector r(ν|II) = (d(ν,P1),d(ν,P2),···,d(ν,Pt)), where d(ν,Pi), 1 ≤ i ≤ t, represents the distance between the vertex ν and the set Pi, that is d(ν, Pi) = minu∈pi{d(ν,u)}. II is a resolving partition for G if for every pair of distinct vertices u, ν of G, r(u|II) ¢ r(ν|II). The partition dimension pd(G) of G is the minimum number of sets in any resolving partition for G. Let G and H be two graphs of order n1 and n2 respectively. The corona product G o H is defined as the graph obtained from G and H by taking one copy of G and n1 copies of H and then joining by an edge, all the vertices from the ith-copy of H with the ith-vertex of G. Here we study the relationship between pd(G o H) and several parameters of the graphs G o H, G and H, including dim(G o H), pd(G) and pd(H).