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

DOI10.1016/J.DAM.2014.08.020MaRDI QIDQ476309zbMATH OpenOpenAlexFDO

Authors Olivier Hudry, Iiro Honkala, Antoine Lobstein

Publication date 28 November 2014

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

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

zbMATH Keywords

identifying codestwin-free graphsidentifiable graphs

Mathematics Subject Classification ID

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

Recommendations

• On the ensemble 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 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• Combinatorial bounds via measure and conquer
• Identifying and locating-dominating codes on chains and cycles
• Identifying codes of Cartesian product of two cliques of the same size
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• 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 ensemble of optimal identifying codes in a twin-free graph
• Total domination in graphs

Cited in

(15)

• Twin subgraphs and core-semiperiphery-periphery structures
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• On the ensemble of optimal identifying codes in a twin-free graph
• Some results about a conjecture on identifying codes in complete suns
• Extremal values for identification, domination and maximum cliques in twin-free graphs.
• Induced paths in twin-free graphs
• Locating-domination and identification
• Structural properties of twin-free graphs
• On Iiro Honkala's contributions to identifying codes
• The identifying code number and functigraphs
• Minimum sizes of identifying codes in graphs differing by one edge
• Minimum sizes of identifying codes in graphs differing by one vertex
• Maximum difference about the size of optimal identifying codes in graphs differing by one vertex
• Extremal values for the maximum degree in a twin-free graph.
• Extension of universal cycles for globally identifying colorings of cycles

This page was built for publication: On the number 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 Q476309)