Locating-Domination and Identification

DOI10.1007/978-3-030-51117-3_8zbMath1479.05281MaRDI QIDQ3384611

Irène Charon, Olivier Hudry, Antoine C. Lobstein

Publication date: 15 December 2021

Published in: Topics in Domination in Graphs (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-51117-3_8

zbMATH Keywords

identifying code; Locating-dominating codes

Mathematics Subject Classification ID

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

Cites Work

• Complexity results for identifying codes in planar graphs
• Liar's domination
• On locating-domination in graphs
• Improved Bounds forr-Identifying Codes of the Hex Grid
• The complexity of computing the covering radius of a code
• On codes identifying vertices in the two-dimensional square lattice with diagonals
• On robust and dynamic identifying codes
• Improved Upper Bounds on Binary Identifying Codes
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• On locating and differetiating-total domination in trees
• Domination and location in acyclic graphs
• On a new class of codes for identifying vertices in graphs
• Sequences of optimal identifying codes
• On Identifying Codes in the Triangular and Square Grids
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Optimal linear identifying codes
• On {ℓ}-Metric Dimensions in Graphs
• On open neighborhood locating-dominating in graphs
• On the Uncertainty of Information Retrieval in Associative Memories
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Identifying Codes in Line Graphs
• Codes for Information Retrieval With Small Uncertainty
• Links Between Discriminating and Identifying Codes in the Binary Hamming Space
• Graphs where every k-subset of vertices is an identifying set
• Minimum density of identifying codes of king grids
• General bounds for identifying codes in some infinite regular graphs
• Identifying codes with small radius in some infinite regular graphs
• Some results about a conjecture on identifying codes in complete suns
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• More results on the complexity of identifying problems in graphs
• The locating chromatic number of the join of graphs
• Identifying path covers in graphs
• Bounds for identifying codes in terms of degree parameters
• On the size of identifying codes in triangle-free graphs
• Locating-total domination in graphs
• Optimal lower bound for 2-identifying codes in the hexagonal grid
• Locally identifying coloring of graphs
• On the number of optimal identifying codes in a twin-free graph
• Maximum size of a minimum watching system and the graphs achieving the bound
• Random subgraphs make identification affordable
• Information retrieval and the average number of input clues
• Identifying codes for infinite triangular grids with a finite number of rows
• Bounds on the locating-total domination number of a tree
• Adaptive identification in Torii in the King lattice
• On binary linear \(r\)-identifying codes
• Identifying codes in some subgraphs of the square lattice
• Identifying codes and locating-dominating sets on paths and cycles
• On covering problems of codes
• On identifying codes in binary Hamming spaces
• On locating--dominating sets in infinite grids
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• Structural properties of twin-free graphs
• Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice
• Locating-dominating codes: bounds and extremal cardinalities
• Discriminating codes in (bipartite) planar graphs
• Identifying codes of cycles with odd orders
• New bounds on binary identifying codes
• Improved bounds on identifying codes in binary Hamming spaces
• New identifying codes in the binary Hamming space
• Minimal identifying codes in trees and planar graphs with large girth
• On the determining number and the metric dimension of graphs
• An optimal strongly identifying code in the infinite triangular grid
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Induced paths in twin-free graphs
• Upper bounds for binary identifying codes
• On \(r\)-locating-dominating sets in paths
• On the size of identifying codes in binary hypercubes
• Liar's domination in graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Graphs of order \(n\) with locating-chromatic number \(n-1\)
• On the complexity of the identification problem in Hamming spaces
• The minimum density of an identifying code in the king lattice.
• Fault-tolerant locating-dominating sets
• Optimal codes for strong identification
• Families of optimal codes for strong identification
• On strongly identifying codes
• On regular and new types of codes for location-domination
• Periodicity of identifying codes in strips
• Bounds on the locating-domination number and differentiating-total domination number in trees
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Polyhedra associated with identifying codes in graphs
• On the minimum size of an identifying code over all orientations of a graph
• Construction of codes identifying sets of vertices
• Line-critical point determining and point distinguishing graphs
• On the density of identifying codes in the square lattice
• On the identification of vertices using cycles
• Identifying and locating-dominating codes on chains and cycles
• Optimal identifying codes in cycles and paths
• Lower bounds for identifying codes in some infinite grids
• Bounds on the identifying codes in trees
• Minimum sizes of identifying codes in graphs differing by one edge
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Erratum to ``Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs.
• Locating-dominating codes in paths
• The compared costs of domination location-domination and identification
• Locating-dominating sets and identifying codes in graphs of girth at least 5
• Optimal open-locating-dominating sets in infinite triangular grids
• Identifying codes and searching with balls in graphs
• On identifying codes that are robust against edge changes
• Watching systems in the King grid
• Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
• New bounds for (\(r, \leq 2\))-identifying codes in the infinite king grid
• Minimum sizes of identifying codes in graphs differing by one vertex
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Neighbor sum distinguishing total coloring of 2-degenerate graphs
• A linear-time algorithm for the identifying code problem on block graphs
• Extremal graphs for the identifying code problem
• An optimal locating-dominating set in the infinite triangular grid
• An improved lower bound for \((1,\leq 2)\)-identifying codes in the king grid
• Choice identification of a graph
• Nordhaus-Gaddum bounds for locating domination
• Watching systems in graphs: an extension of identifying codes
• New lower bound for 2-identifying code in the square grid
• New bounds on the minimum density of an identifying code for the infinite hexagonal grid
• Locating sensors in paths and cycles: the case of 2-identifying codes
• Identifying codes of cycles
• Discrete sensor placement problems in distribution networks
• Monotonicity of the minimum cardinality of an identifying code in the hypercube
• A linear algorithm for minimum 1-identifying codes in oriented trees
• Locating and total dominating sets in trees
• Optimal locating-total dominating sets in strips of height 3
• Point determination in graphs
• On adjacent-vertex-distinguishing total coloring of graphs
• Bounds for Codes Identifying Vertices in the Hexagonal Grid
• Minimum-Density Identifying Codes in Square Grids