Extremal graphs for the identifying code problem

DOI10.1016/j.ejc.2011.01.002zbMath1226.05193arXiv1004.5230OpenAlexW2034175063MaRDI QIDQ2430979

Aline Parreau, Matjaž Kovše, Florent Foucaud, Petru Valicov, Reza Naserasr, Eleonora Guerrini

Publication date: 8 April 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.5230

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Bounds on codes (94B65) Other types of codes (94B60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (26)

Revisiting and Improving Upper Bounds for Identifying Codes ⋮ Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets ⋮ Minimum sizes of identifying codes in graphs differing by one vertex ⋮ The \textsc{red-blue separation} problem on graphs ⋮ Identifying Codes in Line Graphs ⋮ On minimum identifying codes in some Cartesian product graphs ⋮ Identifying codes in vertex-transitive graphs and strongly regular graphs ⋮ Identifying path covers in graphs ⋮ Bounds and extremal graphs for total dominating identifying codes ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ Unnamed Item ⋮ On the size of identifying codes in triangle-free graphs ⋮ Identifying codes and watching systems in Kneser graphs ⋮ Locating-dominating sets in twin-free graphs ⋮ Maximum size of a minimum watching system and the graphs achieving the bound ⋮ Information retrieval and the average number of input clues ⋮ Operads of finite posets ⋮ On the minimum size of an identifying code over all orientations of a graph ⋮ The identifying code number and Mycielski's construction of graphs ⋮ Unnamed Item ⋮ Minimum sizes of identifying codes in graphs differing by one edge ⋮ The compared costs of domination location-domination and identification ⋮ Characterizing extremal graphs for open neighbourhood location-domination ⋮ Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs ⋮ Locating-Domination and Identification ⋮ Unnamed Item

Cites Work

• Extremal cardinalities for identifying and locating-dominating codes in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• Structural properties of twin-free graphs
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Computing roots of graphs is hard
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Identifying and locating-dominating codes on chains and cycles
• Induced subsets
• On a new class of codes for identifying vertices in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Extremal graphs for the identifying code problem