On the Existence of t-Identifying Codes in Undirected De Bruijn Networks

Abstract

This paper proves the existence of t-identifying codes on the class of undirected de Bruijn graphs with string length n and alphabet size d, referred to as B(d, n). It is shown that B(d, n) is t-identifiable whenever d is greater than or equal to 3 and n is greater than or equal to 2t, and t is greater than or equal to 1, or d is greater than or equal to 3, n is greater than or equal to 3, and t = 2, or d = 2, n is greater than or equal to 3, and t = 1. The remaining cases remain open. Additionally, we show that the eccentricity of the undirected non-binary de Bruijn graph is n.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 04, 2015
Accession Number
AD1003126

Entities

People

  • Victoria Horan

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Air Force Research Laboratories
  • Alphabets
  • Department Of Defense
  • Detectors
  • Eccentricity
  • Equations
  • Government Employees
  • Governments
  • Graph Theory
  • Information Operations
  • Military Research
  • Smoke Detectors

Fields of Study

  • Mathematics

Readers

  • Computer Programming and Software Development.
  • Graph Algorithms and Convex Optimization.