The minimum identifying code graphs

DOI10.1016/J.DAM.2012.01.015zbMATH Open1278.94095OpenAlexW2082764347MaRDI QIDQ423972FDOQ423972

Li-Da Tong, André Raspaud

Publication date: 30 May 2012

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

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

Recommendations

• Extremal graphs for the identifying code problem
• Minimum identifying codes in some graphs differing by matchings
• On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
• Identifying codes in some subgraphs of the square lattice
• scientific article; zbMATH DE number 2186985

zbMATH Keywords

identifying codes of graphsminimum identifying code graphpower set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Other types of codes (94B60)

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?)
• On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)

Cited In (6)

• The identifying code number and Mycielski's construction of graphs
• Choice identification of a graph
• Constructing codes identifying sets of vertices
• Title not available (Why is that?)
• Construction of codes identifying sets of vertices
• A comparison of approaches for finding minimum identifying codes on graphs

This page was built for publication: The minimum identifying code graphs

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