On the Identification of Vertices Using Cycles

Abstract

A set of cycles $C_1,\ldots ,C_k$ in a graph $G$ is said to identify the vertices $v$ if the sets $\{j:v\in C_j\}$ are all nonempty and different. In this paper, bounds for the minimum possible $k$ are given when $G$ is the graph ${\bf Z}_p^n$ endowed with the Lee or Hamming metric or $G$ is a complete bipartite graph.