The partition dimension of strong product graphs and Cartesian product graphs

Abstract

Let $G=(V,E)$ be a connected graph. The distance between two vertices $u,v\in V$, denoted by $d(u, v)$, is the length of a shortest $u,v$-path in $G$. The distance between a vertex $v\in V$ and a subset $P\subset V$ is defined as $\min\{d(v, x): x \in 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$ is the minimum number of sets in any resolving partition of $G$. 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.