A note on the partition dimension of Cartesian product graphs

摘要

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 {P1, P2, … , Pt} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P1), d(v, P2), … , d(v, Pt)) 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.