On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)

DOI10.1016/j.dam.2006.03.011zbMath1100.94032OpenAlexW2002611253MaRDI QIDQ2506367

Julien Moncel

Publication date: 28 September 2006

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

Full work available at URL: https://doi.org/10.1016/j.dam.2006.03.011

zbMATH Keywords

fault detectiongraph theoryidentifying codes

Mathematics Subject Classification ID

Applications of graph theory (05C90) Fault detection; testing in circuits and networks (94C12)

Related Items

Identifying Codes in Hereditary Classes of Graphs and VC-Dimension, Identifying Codes in Line Graphs, Identifying codes in vertex-transitive graphs and strongly regular graphs, Fault tolerant detectors for distinguishing sets in graphs, The minimum identifying code graphs, On the size of identifying codes in triangle-free graphs, Unnamed Item, Liar's domination, Minimum identifying codes in some graphs differing by matchings, Open-independent, open-locating-dominating sets

Cites Work

• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Construction of codes identifying sets of vertices
• Identifying Codes and Covering Problems
• On a new class of codes for identifying vertices in graphs
• Unnamed Item