Locating sensors in paths and cycles: The case of 2-identifying codes

David L. Roberts, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

For a graph G and a set D ⊆ V (G), define Nr [x] = {xi ∈ V (G) : d (x, xi) ≤ r} (where d (x, y) is graph theoretic distance) and Dr (x) = Nr [x] ∩ D. D is known as an r-identifying code if for every vertex x, Dr (x) ≠ 0{combining long solidus overlay}, and for every pair of vertices x and y, x ≠ y ⇒ Dr (x) ≠ Dr (y). The various applications of these codes include attack sensor placement in networks and fault detection/localization in multiprocessor or distributed systems. Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969-987] and Gravier et al. [S. Gravier, J. Moncel, A. Semri, Identifying codes of cycles, European Journal of Combinatorics 27 (2006) 767-776] provide partial results about the minimum size of D for r-identifying codes for paths and cycles and present complete closed form solutions for the case r = 1, based in part on Daniel [M. Daniel, Codes identifiants, Rapport pour le DEA ROCO, Grenoble, June 2003]. We provide complete solutions for the case r = 2.

Original languageEnglish (US)
Pages (from-to)72-82
Number of pages11
JournalEuropean Journal of Combinatorics
Volume29
Issue number1
DOIs
StatePublished - Jan 2008

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Locating sensors in paths and cycles: The case of 2-identifying codes'. Together they form a unique fingerprint.

Cite this