Accession Number:

AD1003119

Title:

Identifying Codes on Directed De Bruijn Graphs

Descriptive Note:

OSTP Journal Article

Corporate Author:

Air Force Research Laboratory/RITF ROME United States

Personal Author(s):

• Boutin,Debra
• Horan,Victoria
• Pelto,Mikko

Report Date:

2015-08-27

Pagination or Media Count:

27.0

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 Bd, 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.

Descriptors:

• graph theory
• GRAPHS
• MATHEMATICS

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE