On the ensemble of optimal identifying codes in a twin-free graph

DOI10.1007/S12095-015-0148-3MaRDI QIDQ267807zbMATH OpenOpenAlexFDO

Authors Olivier Hudry, Iiro Honkala, Antoine Lobstein

Publication date 11 April 2016

Published in Cryptography and Communications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s12095-015-0148-3

zbMATH Keywords

identifying codestwin-free graphsidentifiable graphsJohnson graphsJohnson induced subgraphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial codes (94B25)

Recommendations

• On the number of optimal identifying codes in a twin-free graph
• Minimum sizes of identifying codes in graphs differing by one vertex
• Structural properties of twin-free graphs
• Minimum sizes of identifying codes in graphs differing by one edge
• Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Graphs where every \(k\)-subset of vertices is an identifying set
• Induced subgraphs of Johnson graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On \((r,\leq 2)\)-locating-dominating codes in the infinite King grid
• On a new class of codes for identifying vertices in graphs
• On the ensemble of optimal dominating and locating-dominating codes in a graph
• On the number of optimal identifying codes in a twin-free graph

Cited in

(9)

• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• On the number of optimal identifying codes in a twin-free graph
• Induced paths in twin-free graphs
• On Iiro Honkala's contributions to identifying codes
• On the ensemble of optimal dominating and locating-dominating codes in a graph
• Minimum sizes of identifying codes in graphs differing by one edge
• Minimum sizes of identifying codes in graphs differing by one vertex
• Which graphs occur as \(\gamma\)-graphs?
• Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

This page was built for publication: On the ensemble of optimal identifying codes in a twin-free graph

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