RT journal article
T1 The partition dimension of strong product graphs and Cartesian product graphs
A1 González Yero, Ismael
A1 Jakovac, Marko
A1 Kuziak, Dorota
A1 Taranenko, Andrej
A2 Estadística e Investigación Operativa
A2 Matemáticas
K1 Resolving partition
K1 partition dimension
K1 strong product graphs
K1 Cartesian product graphs
K1 graphs partitioning
AB 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 avertex $v\in V$ and a subset $P\subset V$ is defined as $\min\{d(v, x): x \in P\}$, andit is denoted by $d(v, P)$. An ordered partition $\{P_1,P_2, ...,P_t\}$ of vertices of agraph $G$, is a resolving partition of $G$, if all the distancevectors $(d(v,P_1),d(v,P_2),...,d(v,P_t))$ are different. The partition dimension of $G$ is the minimum number ofsets in any resolving partition of $G$. In this article we study the partitiondimension 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.
PB Elsevier
SN 0012-365X
YR 2014
FD 2014-09-28
LK http://hdl.handle.net/10498/30924
UL http://hdl.handle.net/10498/30924
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 10-may-2026