The partition dimension of strong product graphs and Cartesian product graphs

Let G=(V,E)G=(V,E) be a connected graph. The distance between two vertices u,v∈Vu,v∈V, denoted by d(u,v)d(u,v), is the length of a shortest u,vu,v-path in GG. The distance between a vertex v∈Vv∈V and a subset P⊂VP⊂V is defined as min{d(v,x):x∈P}min{d(v,x):x∈P}, and it is denoted by d(v,P)d(v,P). An ordered partition {P1,P2,…,Pt}{P1,P2,…,Pt} of vertices of a graph GG, is a resolving partition of GG, if all the distance vectors (d(v,P1),d(v,P2),…,d(v,Pt))(d(v,P1),d(v,P2),…,d(v,Pt)) are different. The partition dimension of GG is the minimum number of sets in any resolving partition of GG. In this article we study the partition dimension of strong product graphs and Cartesian product graphs. Specifically, we prove that the partition dimension of the strong product of graphs is bounded below by four and above by the product of the partition dimensions of the factor graphs. Also, we give the exact value of the partition dimension of strong product graphs when one factor is a complete graph and the other one is a path or a cycle. For the case of Cartesian product graphs, we show that its partition dimension is less than or equal to the sum of the partition dimensions of the factor graphs minus one. Moreover, we obtain an upper bound on the partition dimension of Cartesian product graphs, when one factor is a complete graph.