On graphs on n vertices having an identifying code of cardinality _2(n+1)

DOI10.1016/J.DAM.2006.03.011zbMATH Open1100.94032OpenAlexW2002611253MaRDI QIDQ2506367FDOQ2506367

Authors: 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

Recommendations

• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• On graphs admitting codes identifying sets of vertices
• scientific article; zbMATH DE number 2186985
• On a new class of identifying codes in graphs
• On a new class of codes for identifying vertices in graphs
• The identifying code number and Mycielski's construction of graphs
• On the size of identifying codes in triangle-free graphs
• Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code
• On the minimum size of an identifying code over all orientations of a graph
• Identifying codes in vertex-transitive graphs and strongly regular graphs

zbMATH Keywords

graph theoryfault detectionidentifying codes

Mathematics Subject Classification ID

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

Cites Work

• 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
• Construction of codes identifying sets of vertices
• Title not available (Why is that?)
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Identifying Codes and Covering Problems

Cited In (15)

• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• Identifying codes in hereditary classes of graphs and VC-dimension
• Codes identifying sets of vertices in random networks
• Liar's domination
• On the size of identifying codes in triangle-free graphs
• Minimum identifying codes in some graphs differing by matchings
• Optimal identifying codes in cycles and paths
• Construction of codes identifying sets of vertices
• The minimum identifying code graphs
• Identifying codes in line graphs
• Fault tolerant detectors for distinguishing sets in graphs
• Open-independent, open-locating-dominating sets
• Commutative rings introduce a class of identifiable graphs
• Edge identifying codes
• Identifying codes in vertex-transitive graphs and strongly regular graphs

This page was built for publication: On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)

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