A note on the partition dimension of Cartesian product graphs
Abstract Let G  = ( V ,  E ) be a connected graph. The distance between two vertices u , v  ∈  V , denoted by d ( u ,  v ), is the length of a shortest u  −  v path in G . The distance between a vertex v  ∈  V and a subset P  ⊂  V is defined as min { d ( v , x ) : x ∈ P } , and it is denoted by d ( v ,  P ). An ordered partition { P 1 ,  P 2 , … ,  P t } of vertices of a graph G , is a resolving partition of G , if all the distance vectors ( d ( v ,  P 1 ),  d ( v ,  P 2 ), … ,  d ( v ,  P t )) are different. The partition dimension of G , denoted by pd ( G ), is the minimum number of sets in any resolving partition of G . In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G , H , pd ( G  ×  H ) ⩽  pd ( G ) +  pd ( H ) and pd ( G  ×  H ) ⩽  pd ( G ) +  dim ( H ), where dim ( H ) denotes the metric dimension of H . Consequently, we show that pd ( G  ×  H ) ⩽  dim ( G ) +  dim ( H ) + 1.