Some relations between the partition dimension and the twin number of a graph

Carmen Hernando
Universitat Polit\`ecnica de Catalunya

Merc\`e Mora
Universitat Polit\`ecnica de Catalunya

Ignacio M. Pelayo
Universitat Polit\`ecnica de Catalunya



Content: Let $\Pi$ be a partition of the set of vertices of a graph $G$. We denote by $r(u|\Pi)$ the vector of distances from vertex $u$ to the parts of $\Pi$. The partition $\Pi$ is a \emph{resolving partition} of $G$ if $r(u,\Pi)\neq r(v,\Pi)$ for every pair of distinct vertices $u$, $v$. The \emph{partition dimension} $\beta_p(G)$ of $G$ is the minimum size of a resolving partition of $G$. Two vertices $u,v$ of $G$ are called \emph{twins} if they have exactly the same set of neighbors other than $u$ and $v$. It is easy to prove that the twin relation defines an equivalence relation on the set of vertices of a graph. An equivalence class of the twin relation will be referred to as a \emph{twin class}. The \emph{twin number} $\tau (G)$ of $G$ is the maximum size of a twin class of $G$. In this talk, we study the relation between the twin number and the partition dimension of a graph. By the one hand, we focus our attention on the case of graphs having a twin number at least half its order. In this case, an upper bound for the partition dimension in terms of the twin number is given. From here, we revisit some results about graphs with partition dimension almost its order. By the other hand, we show that, in general, the ratio between the partition dimension and the twin number is not bounded by any constant.

Back to all abstracts