On identifying codes that are robust against edge changes

Assume that G =(V, E) is an undirected graph, and C ⊆ V. For every v ∈ V, denote I r(G; v)={u ∈ C: d(u, v)≤ r}, where d(u, v) denotes the number of edges on any shortest path from u to v in G. If all the sets I r(G; v) for v ∈ V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r =1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide.

Authors

• Iiro Honkala
• Tero Laihonen

Keywords

• Identifying code
• Fault tolerance
• Robustness
• Edge changes
• Optimal code
• Multiprocessor system
• Graphs