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
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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