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

A set of subgraphs C 1, C 2,…, C k in a graph G is said to identify the vertices (resp. the edges) if the sets {j : v∈C j} (resp. {j : e∈C j} ) 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 C i are required to be...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2003-08, Vol.129 (2), p.409-419
Main Authors: Honkala, Iiro, Karpovsky, Mark G., Litsyn, Simon
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A set of subgraphs C 1, C 2,…, C k in a graph G is said to identify the vertices (resp. the edges) if the sets {j : v∈C j} (resp. {j : e∈C j} ) 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 C i 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(02)00579-6