Properties of Corona Product Graphs

Abstract

Given a set of vertices $S=\{v_1,v_2,\dots ,v_k\}$ of a connected graph $G$, the metric representation of a vertex $v$ of $G$ with respect to $S$ is the vector $r(v|S)=(d(v,v_1),d(v,v_2),\dots ,d(v,v_k))$, where $d(v,v_i)$, $i\in \{1,\dots ,k\}$, denotes the distance between $v$ and $v_i$. $S$ is a resolving set of $G$ if for every pair of distinct vertices $u,v$ of $G$, $r(u|S)\ne r(v|S)$. The metric dimension $\dim (G)$ of $G$ is the minimum cardinality of any resolving set of $G$. Given an ordered partition $\mathrm{\Pi }=\{P_1,P_2,\dots ,P_t\}$ of vertices of a connected graph $G$, the partition representation of a vertex $v$ of $G$, with respect to the partition $\mathrm{\Pi }$, is the vector $r(v|\mathrm{\Pi })=(d(v,P_1),d(v,P_2),\dots ,d(v,P_t))$, where $d(v,P_i)$, $1\le i\le t$, represents the distance between the vertex $v$ and the set $P_i$, that is $d(v,P_i)=\underset{u\in P_i}{min}\{d(v,u)\}$. $\mathrm{\Pi }$ is a resolving partition for $G$ if for every pair of distinct vertices $u,v$ of $G$, $r(u|\mathrm{\Pi })\ne r(v|\mathrm{\Pi })$. The partition dimension $\mathrm{p}\mathrm{d}(G)$ of $G$ is the minimum number of sets in any resolving partition for $G$. Let $G$ and $H$ be two graphs of order $n$ and $m$, respectively. The corona product $G\odot H$ is defined as the graph obtained from $G$ and $H$ by taking one copy of $G$ and $n$ copies of $H$ and then joining, by an edge, all the vertices from the $i$-th copy of $H$ with the $i$-th vertex of $G$. Here, we study the relationship between $\mathrm{p}\mathrm{d}(G\odot H)$ and several parameters of the graphs $G\odot H$, $G$, and $H$, including $\dim (G\odot H)$, $\mathrm{p}\mathrm{d}(G)$, and $\mathrm{p}\mathrm{d}(H)$.