Identifying and locating-dominating codes on chains and cycles

DOI10.1016/j.ejc.2003.12.013zbMath1053.05095MaRDI 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

zbMATH Keywords

\(r\)-identifying code; \(r\)-locating-dominating code

Mathematics Subject Classification ID

94B65: Bounds on codes

94B60: Other types of codes

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Minimum identifying codes in some graphs differing by matchings, Open-independent, open-locating-dominating sets, Revisiting and Improving Upper Bounds for Identifying Codes, LD-graphs and global location-domination in bipartite graphs, A polyhedral approach to locating-dominating sets in graphs, On the size of identifying codes in triangle-free graphs, On the number of optimal identifying codes in a twin-free graph, Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds., Extension of universal cycles for globally identifying colorings of cycles, Partial linear spaces and identifying codes, Identification in \(\mathbb Z^2\) using Euclidean balls, Identifying codes and locating-dominating sets on paths and cycles, On locating--dominating sets in infinite grids, Identifying codes in vertex-transitive graphs and strongly regular graphs, Fault tolerant detectors for distinguishing sets in graphs, Locating-dominating codes: bounds and extremal cardinalities, Identifying codes of cycles with odd orders, On \(r\)-locating-dominating sets in paths, Locating-dominating sets in hypergraphs, Identifying codes in the direct product of a complete graph and some special graphs, Progress on the description of identifying code polyhedra for some families of split graphs, Polyhedra associated with identifying codes in graphs, Optimal identifying codes in cycles and paths, Bounds on the identifying codes in trees, Minimum sizes of identifying codes in graphs differing by one edge, Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code, On locating-dominating set of regular graphs, Locating and identifying codes in dihedral graphs, Open locating-dominating sets in circulant graphs, Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs, The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations, Optimal identifying codes of two families of Cayley graphs, Linear-time algorithms for three domination-based separation problems in block graphs, Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes, Covering codes of a graph associated with a finite vector space, New results of identifying codes in product graphs, Locating-dominating codes in paths, On two variations of identifying codes, Optimal bounds on codes for location in circulant graphs, Locating-dominating sets of functigraphs, Locating-dominating sets and identifying codes in graphs of girth at least 5, Locating-paired-dominating sets in square grids, On identifying codes that are robust against edge changes, New results on variants of covering codes in Sierpiński graphs, Minimum sizes of identifying codes in graphs differing by one vertex, A linear-time algorithm for the identifying code problem on block graphs, Locating domination in bipartite graphs and their complements, Extremal graphs for the identifying code problem, An optimal locating-dominating set in the infinite triangular grid, Identifying codes of the direct product of two cliques, Optimal identifying codes in the infinite 3-dimensional king grid, Watching systems in graphs: an extension of identifying codes, Locating and identifying codes in circulant networks, Identifying codes of corona product graphs, Locating sensors in paths and cycles: the case of 2-identifying codes, Identifying codes of cycles, A linear algorithm for minimum 1-identifying codes in oriented trees, Fault-tolerant detectors for distinguishing sets in cubic graphs, Complexity results for identifying codes in planar graphs, Liar's domination, Locating-Domination and Identification

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