Ruxandra Marinescu-Ghemeci and Ioan Tomescu: On star partition dimension of the generalized gear graph, p.261-268

Abstract:

For a connected graph $G$ and any two vertices $u$ and $v$ in $G$, let $d(u,v)$ denote the distance between $u$ and $v$. For a subset $S$ of $V(G)$, the distance between a vertex $v$ and $S$ is $d(v,S)=\mbox{min}\{d(v,x)\mid x\in S\}$. For an ordered $k$-partition of $V(G)$ $\Pi=\{S_1, S_2, \ldots , S_k\}$ and a vertex $v$, the representation of $v$ with respect to $\Pi$ is the $k$-vector $r(v\mid \Pi)=(d(v,S_1), d(v,S_2), \ldots % d(v,S_k))$. $\Pi$ is a resolving partition for $G$ if the $k$-vectors $r(v\mid \Pi)$, $v\in V(G)$ are distinct. The minimum $k$ for which there exists a resolving $k$-partition of $V(G)$ is the partition dimension of $G$, denoted by $\mbox{pd}(G)$. $\Pi=\{S_1, S_2, \ldots , S_k\}$ is a star resolving $k$-partition for $G$ if it is a resolving partition and each subgraph induced by $S_i$, $1\le i\le k$, is a star. The minimum $k$ for which there exists a star resolving $k$-partition of $V(G)$ is the star partition dimension of $G$, denoted by $\mbox{spd}(G)$.

Let $J_{k,n}$ be the graph obtained from the wheel $W_{kn}$ by keeping spokes with step $k$, for $k\ge 2$ and $n\ge 2$. In this paper the star partition dimension for this family of graphs is determined.

Key Words: Distance, resolving partition, star resolving partition, partition dimension, star partition dimension, gear graph.

2000 Mathematics Subject Classification: Primary: 05C12;
Secondary: 05C35.

Download the paper in pdf format here.