Extremal graphs for the identifying code problem
From MaRDI portal
Publication:2430979
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
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
