On the $k$-partition dimension of graphs

Abstract

As a generalization of the concept of the partition dimension of a graph, this article introduces the notion of the $k$-partition dimension. Given a nontrivial connected graph $G=(V,E)$, a partition $\Pi$ of $V$ is said to be a $k$-partition generator for $G$ if any pair of different vertices $u,v\in V$ is distinguished by at least $k$ vertex sets of $\Pi$, \emph{i.e}., there exist at least $k$ vertex sets $S_1,\dots ,S_k\in \Pi$ such that $d(u,S_i)\ne d(v,S_i)$ for every $i\in \{1,\dots ,k\}$. A $k$-partition generator for $G$ with minimum cardinality among all their $k$-partition generators is called a $k$-partition basis of $G$ and its cardinality the $k$-partition dimension of $G$. A nontrivial connected graph $G$ is $k$-partition dimensional if $k$ is the largest integer such that $G$ has a $k$-partition basis. We give a necessary and sufficient condition for a graph to be $r$-partition dimensional and we obtain several results on the $k$-partition dimension for $k\in \{1,\dots ,r\}$.

19 pages, 3 figures