Identifying and locating-dominating codes on chains and cycles

DOI10.1016/J.EJC.2003.12.013zbMATH Open1053.05095OpenAlexW2037221311MaRDI QIDQ1883609FDOQ1883609

Authors: Nathalie Bertrand, Irène Charon, Olivier Hudry, Antoine 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

Recommendations

• Identifying codes and locating-dominating sets on paths and cycles
• Locating-dominating codes in cycles
• Locating-domination and identifying codes in trees
• Approximability of identifying codes and locating-dominating codes
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Locating-dominating codes in paths
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Independent locating-dominating sets and identifying codes in graphs
• Locating and identifying codes in circulant graphs
• Identifying and locating-dominating codes in (random) geometric networks

zbMATH Keywords

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

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Bounds on codes (94B65) Other types of codes (94B60)

Cites Work

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On identification in \(\mathbb Z^2\) using translates of given patterns
• The minimum density of an identifying code in the king lattice.
• Identifying codes with small radius in some infinite regular graphs

Cited In (75)

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

This page was built for publication: Identifying and locating-dominating codes on chains and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1883609)