Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori Original Research Article

A set of subgraphs C1,C2,…,Ck in a graph G is said to identify the vertices (resp. the edges) if the sets {j: v∈Cj} (resp. {j: e∈Cj}) are nonempty for all the vertices v (edges e) and no two are the same set. We consider the problem of minimizing k when the subgraphs Ci are required to be cycles or closed walks. The motivation comes from maintaining multiprocessor systems, and we study the cases when G is the binary hypercube, or the two-dimensional p-ary space endowed with the Lee metric.