19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
On the partition dimension of corona graphs
Presented by Mr. Ismael GONZALEZ YERO
Type: Oral presentation
Track: Metric Graph Theory
Content
Given a set of vertices $S=\{v_1,v_2,...,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),...,d(v,v_k))$,
where $d(v,v_i)$, $i\in \{1,...,k\}$ denotes the distance between
$v$ and $v_i$. $S$ is a resolving set of $G$ if for every pair of
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 $\Pi =\{P_1,P_2, ...,P_t\}$ of
vertices of a connected graph $G$, the partition representation of a
vertex $v$ of $G$, with respect to the partition $\Pi$ is the vector
$r(v|\Pi)=(d(v,P_1),d(v,P_2),...,d(v,P_t))$, where $d(v,P_i)$,
$1\leq i\leq t$, represents the distance between the vertex $v$ and
the set $P_i$, that is $d(v,P_i)=\min_{u\in P_i}\{d(v,u)\}$. $\Pi$
is a resolving partition for $G$ if for every pair of vertices $u,v$
of $G$, $r(u|\Pi)\ne r(v|\Pi)$. The partition dimension $pd(G)$ of
$G$ is the minimum number of sets in any resolving partition for $G$.
In this work we study the partition dimension of corona graphs. Particularly, we obtain some bounds on the partition dimension, we give some relationships between the metric dimension and partition dimension and we deduce some exact values of some particular cases of corona graphs.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Primary authors
- Mr. Ismael GONZALEZ YERO Universitat Rovira i Virgili
- Prof. Juan Alberto RODRIGUEZ-VELAZQUEZ Universitat Rovira i Virgil
- Mrs. Dorota KUZIAK Gda\'nsk University of Technology