Identifying Codes on Directed De Bruijn Graphs

Abstract

For a directed graph G, a t-identifying code is a subset S reflex subset contained in V (G) with the property that for each vertex v a member V (G) the set of vertices of S reachable from v by a directed path of length at most t is both non-empty and unique. A graph is called t-identifiable if there exists a t-identifying code. This paper shows that the directed de Bruijn graph B(d, n) is t-identifiable for n is greater than or equal to 2t1, and is not t-identifiable for n is less than or equal to 2t2.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 27, 2015
Accession Number
AD1003119

Entities

People

  • Debra Boutin
  • Mikko Pelto
  • Victoria Horan

Tags

Communities of Interest

  • Sensors

DTIC Thesaurus Topics

  • Air Force
  • Air Force Research Laboratories
  • Construction
  • Department Of Defense
  • Detectors
  • Government Employees
  • Governments
  • Graph Theory
  • Information Operations
  • Mathematics
  • Military Research
  • Notation
  • Numbers
  • Permutations
  • Sensor Networks
  • Smoke Detectors
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.