Identifying Codes on Directed De Bruijn Graphs
Abstract
For a directed graph G, a t-identifying code is a subset S V (G) with the property that for each vertex v 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 de Bruijn graph ~B (d, n) is 1- and 2-identifiable and examines conditions under which it is not t-identifiable. This paper also proves that a t-identifying code for t- identifiable de Bruijn graphs must contain at least dn 1(d 1) vertices. Constructions are given to show that this lower bound is achievable for 1-identifying codes when n is odd, or n is even and d > 2, and for 2-identifying codes when n > 3.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 19, 2014
- Accession Number
- ADA623527
Entities
People
- Debra Boutin
- Victoria Horan
Organizations
- Air Force Research Laboratory