Extremal graphs for the identifying code problem
From MaRDI portal
Publication:2430979
DOI10.1016/j.ejc.2011.01.002zbMath1226.05193arXiv1004.5230MaRDI 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
05C35: Extremal problems in graph theory
05C90: Applications of graph theory
94B65: Bounds on codes
94B60: Other types of codes
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Unnamed Item, Identifying Codes in Line Graphs, Identifying path covers in graphs, On the size of identifying codes in triangle-free graphs, Maximum size of a minimum watching system and the graphs achieving the bound, Information retrieval and the average number of input clues, Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs, Identifying codes in vertex-transitive graphs and strongly regular graphs, Locating-dominating sets in twin-free graphs, Operads of finite posets, On the minimum size of an identifying code over all orientations of a graph, Minimum sizes of identifying codes in graphs differing by one edge, The compared costs of domination location-domination and identification, 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, On minimum identifying codes in some Cartesian product graphs, Unnamed Item, Identifying codes and watching systems in Kneser graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
