Extremal cardinalities for identifying and locating-dominating codes in graphs
From MaRDI portal
Publication:864121
DOI10.1016/j.disc.2005.09.027zbMath1113.05075OpenAlexW2046561241MaRDI QIDQ864121
Irène Charon, Olivier Hudry, Antoine C. Lobstein
Publication date: 13 February 2007
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2005.09.027
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial codes (94B25)
Related Items
On locating--dominating sets in infinite grids ⋮ Watching systems in the King grid ⋮ 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 graphs having a \(V\setminus \{x\}\) set as an identifying code ⋮ Identifying Codes in Line Graphs ⋮ Optimal identifying codes in cycles and paths ⋮ Bounds and extremal graphs for total dominating identifying codes ⋮ Locally identifying colourings for graphs with given maximum degree ⋮ Identification in \(\mathbb Z^2\) using Euclidean balls ⋮ Locating-dominating codes: bounds and extremal cardinalities ⋮ On the binary locating-domination number of regular and strongly-regular graphs ⋮ Extremal graphs for the identifying code problem ⋮ On the size of identifying codes in triangle-free graphs ⋮ Identifying codes and watching systems in Kneser graphs ⋮ The binary locating-dominating number of some convex polytopes ⋮ On the sizes of graphs and their powers: the undirected case ⋮ Watching systems in graphs: an extension of identifying codes ⋮ Locally identifying coloring in bounded expansion classes of graphs ⋮ Maximum size of a minimum watching system and the graphs achieving the bound ⋮ New bounds on binary identifying codes ⋮ Improved bounds on identifying codes in binary Hamming spaces ⋮ On binary linear \(r\)-identifying codes ⋮ Unnamed Item ⋮ Minimum sizes of identifying codes in graphs differing by one edge ⋮ Locating-dominating codes in paths ⋮ On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\) ⋮ The compared costs of domination location-domination and identification ⋮ Minimum identifying codes in some graphs differing by matchings ⋮ Upper bounds for binary identifying codes ⋮ Locating-Domination and Identification ⋮ On the size of identifying codes in binary hypercubes ⋮ Unnamed Item ⋮ Combinatorial identification problems and graph powers ⋮ Binary locating-dominating sets in rotationally-symmetric convex polytopes ⋮ On the Structure of Identifiable Graphs
Cites Work
- On graphs having a \(V\setminus \{x\}\) set as an identifying code
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- On a new class of codes for identifying vertices in graphs
- Identifying codes with small radius in some infinite regular graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Extremal cardinalities for identifying and locating-dominating codes in graphs