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

DOI10.1007/s12095-015-0148-3zbMath1333.05222OpenAlexW1456675268MaRDI QIDQ267807

Olivier Hudry, Antoine C. Lobstein, Iiro S. Honkala

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 codesJohnson graphstwin-free graphsidentifiable graphsJohnson induced subgraphs

Mathematics Subject Classification ID

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

Related Items (4)

Which graphs occur as \(\gamma\)-graphs? ⋮ On the number of optimal identifying codes in a twin-free graph ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ On the ensemble of optimal dominating and locating-dominating codes in a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On \((r,\leq 2)\)-locating-dominating codes in the infinite King grid
• Induced subgraphs of Johnson graphs
• On the number of optimal identifying codes in a twin-free graph
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On the ensemble of optimal dominating and locating-dominating codes in a graph
• On a new class of codes for identifying vertices in graphs
• Graphs where every k-subset of vertices is an identifying set

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