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

✍ Scribed by Iiro Honkala; Mark G. Karpovsky; Simon Litsyn

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 272 KB
• Volume: 129
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00579-6

✦ Synopsis

A set of subgraphs C1; C2; : : : ; C k 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.