Identifying codes on directed de Bruijn graphs

DOI10.1016/J.DAM.2019.02.005MaRDI QIDQ2416416zbMATH OpenOpenAlexWikidataFDO

Authors Victoria Horan Goliber, Mikko Pelto, Debra L. Boutin

Publication date 23 May 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.5842

zbMATH Keywords

dominating setdetermining setidentifying codesresolving setde Bruijn network

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Paths and cycles (05C38) Theory of error-correcting codes and error-detecting codes (94B99)

Abstract: For a directed graph $G$, a $t$-identifying code is a subset $SsubseteqV(G)$ with the property that for each vertex $vinV(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 {it $t$-identifiable} if there exists a $t$-identifying code. This paper shows that the de~Bruijn graph $vecmathcalB(d,n)$ is $t$-identifiable if and only if $ngeq2t-1$. It is also shown that a $t$-identifying code for $t$-identifiable de~Bruijn graphs must contain at least $d^{n-1}(d-1)$ vertices, and constructions are given to show that this lower bound is achievable $ngeq2t$. Further a (possibly) non-optimal construction is given when $n=2t-1$. Additionally, with respect to $vecmathcalB(d,n)$ we provide upper and lower bounds on the size of a minimum extit{$t$-dominating set} (a subset with the property that every vertex is at distance at most $t$ from the subset), that the minimum size of a extit{directed resolving set} (a subset with the property that every vertex of the graph can be distinguished by its directed distances to vertices of $S$) is $d^{n-1}(d-1)$, and that if $d>n$ the minimum size of a {it determining set} (a subset $S$ with the property that the only automorphism that fixes $S$ pointwise is the trivial automorphism) is $leftlceilfracd-1nightceil$.

Recommendations

• On the minimum size of an identifying code over all orientations of a graph
• Extremal graphs for the identifying code problem
• The minimum identifying code graphs
• Identifying codes in line digraphs
• On the domination number of $t$-constrained de Bruijn graphs

Cites work

• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 975419 (Why is no real title available?)
• Identifying graph automorphisms using determining sets
• Landmarks in graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On a new class of codes for identifying vertices in graphs
• On the k-tuple domination of de Bruijn and Kautz digraphs
• On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs
• On the metric dimension of line graphs
• Partial words and a theorem of Fine and Wilf
• The algorithm design manual
• The directed distance dimension of oriented graphs
• Uniqueness Theorems for Periodic Functions

Cited in

(2)

• A comparison of approaches for finding minimum identifying codes on graphs
• On weak metric dimension of digraphs

Describes a project that uses

Uses Software

• Stony Brook

This page was built for publication: Identifying codes on directed de Bruijn graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2416416)