Identifying and locating-dominating codes on chains and cycles
From MaRDI portal
Publication:1883609
DOI10.1016/j.ejc.2003.12.013zbMath1053.05095OpenAlexW2037221311MaRDI QIDQ1883609
Nathalie Bertrand, Olivier Hudry, Irène Charon, Antoine C. Lobstein
Publication date: 13 October 2004
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2003.12.013
Bounds on codes (94B65) Other types of codes (94B60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (61)
On locating--dominating sets in infinite grids ⋮ LD-graphs and global location-domination in bipartite graphs ⋮ The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ Revisiting and Improving Upper Bounds for Identifying Codes ⋮ On identifying codes that are robust against edge changes ⋮ A polyhedral approach to locating-dominating sets in graphs ⋮ New results on variants of covering codes in Sierpiński graphs ⋮ Minimum sizes of identifying codes in graphs differing by one vertex ⋮ Optimal identifying codes of two families of Cayley graphs ⋮ Fault-tolerant detectors for distinguishing sets in cubic graphs ⋮ Locating-dominating sets in hypergraphs ⋮ Optimal identifying codes in cycles and paths ⋮ A linear-time algorithm for the identifying code problem on block graphs ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ Identifying codes in vertex-transitive graphs and strongly regular graphs ⋮ Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes ⋮ Fault tolerant detectors for distinguishing sets in graphs ⋮ Locating domination in bipartite graphs and their complements ⋮ Partial linear spaces and identifying codes ⋮ Identification in \(\mathbb Z^2\) using Euclidean balls ⋮ Locating-dominating codes: bounds and extremal cardinalities ⋮ Extremal graphs for the identifying code problem ⋮ On the size of identifying codes in triangle-free graphs ⋮ An optimal locating-dominating set in the infinite triangular grid ⋮ Identifying codes and locating-dominating sets on paths and cycles ⋮ Identifying codes of the direct product of two cliques ⋮ Optimal identifying codes in the infinite 3-dimensional king grid ⋮ Covering codes of a graph associated with a finite vector space ⋮ Watching systems in graphs: an extension of identifying codes ⋮ Locating and identifying codes in circulant networks ⋮ Identifying codes in the direct product of a complete graph and some special graphs ⋮ Identifying codes of corona product graphs ⋮ On the number of optimal identifying codes in a twin-free graph ⋮ Complexity results for identifying codes in planar graphs ⋮ Locating sensors in paths and cycles: the case of 2-identifying codes ⋮ Identifying codes of cycles with odd orders ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ New results of identifying codes in product graphs ⋮ Progress on the description of identifying code polyhedra for some families of split graphs ⋮ Polyhedra associated with identifying codes in graphs ⋮ Extension of universal cycles for globally identifying colorings of cycles ⋮ Bounds on the identifying codes in trees ⋮ Identifying codes of cycles ⋮ Minimum sizes of identifying codes in graphs differing by one edge ⋮ A linear algorithm for minimum 1-identifying codes in oriented trees ⋮ Locating-dominating codes in paths ⋮ On two variations of identifying codes ⋮ Liar's domination ⋮ Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code ⋮ Minimum identifying codes in some graphs differing by matchings ⋮ On locating-dominating set of regular graphs ⋮ Locating-Domination and Identification ⋮ Locating and identifying codes in dihedral graphs ⋮ On \(r\)-locating-dominating sets in paths ⋮ Open locating-dominating sets in circulant graphs ⋮ Optimal bounds on codes for location in circulant graphs ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs ⋮ Locating-dominating sets of functigraphs ⋮ Open-independent, open-locating-dominating sets ⋮ Locating-dominating sets and identifying codes in graphs of girth at least 5 ⋮ Locating-paired-dominating sets in square grids
Cites Work
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- The minimum density of an identifying code in the king lattice.
- 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
- Unnamed Item
- Unnamed Item
This page was built for publication: Identifying and locating-dominating codes on chains and cycles
