On a new class of codes for identifying vertices in graphs

DOI10.1109/18.661507zbMath1105.94342OpenAlexW2100994793MaRDI QIDQ4400275

Mark G. Karpovsky, Lev B. Levitin, Krishnendu Chakrabarty

Publication date: 27 October 1998

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/18.661507

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Fault detection; testing in circuits and networks (94C12) Other types of codes (94B60)

Related Items (only showing first 100 items - show all)

Optimal codes for strong identification ⋮ More results on the complexity of identifying problems in graphs ⋮ Families of optimal codes for strong identification ⋮ On locating--dominating sets in infinite grids ⋮ On the ensemble of optimal identifying codes in a twin-free graph ⋮ Identification of points using disks ⋮ On identifying codes in the Cartesian product of a path and a complete graph ⋮ Recursive methods for some problems in coding and random permutations ⋮ Identifying and locating-dominating codes on chains and cycles ⋮ The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ Identifying codes in the complementary prism of cycles ⋮ Open-independent, open-locating-dominating sets in complementary prism graphs ⋮ On the covering of vertices for fault diagnosis in hypercubes ⋮ A comparison of approaches for finding minimum identifying codes on graphs ⋮ Paths and cycles identifying vertices in twisted cubes ⋮ Extremal cubic graphs for fault-tolerant locating domination ⋮ On the watching number of graphs using discharging procedure ⋮ On a new class of identifying codes in graphs ⋮ Inapproximability of the lid-chromatic number ⋮ Some links between identifying codes and separating, dominating and total dominating sets in graphs ⋮ Constructing codes identifying sets of vertices ⋮ A family of optimal identifying codes in \(\mathbb Z^2\) ⋮ On robust identification in the square and King grids ⋮ Relaxed locally identifying coloring of graphs ⋮ Extremal cardinalities for identifying and locating-dominating codes in graphs ⋮ On graphs having a \(V\setminus \{x\}\) set as an identifying code ⋮ Optimal identifying codes of two families of Cayley graphs ⋮ Identifying codes in some subgraphs of the square lattice ⋮ Codes identifying sets of vertices in random networks ⋮ The \textsc{red-blue separation} problem on graphs ⋮ On regular and new types of codes for location-domination ⋮ Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice ⋮ Optimal identifying codes in cycles and paths ⋮ Identifying codes in vertex-transitive graphs and strongly regular graphs ⋮ Identifying path covers in graphs ⋮ Locally identifying coloring of graphs with few P4s ⋮ Fault tolerant detectors for distinguishing sets in graphs ⋮ Graph classes with and without powers of bounded clique-width ⋮ On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results ⋮ Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. ⋮ Partial linear spaces and identifying codes ⋮ Locally identifying colourings for graphs with given maximum degree ⋮ Identification in \(\mathbb Z^2\) using Euclidean balls ⋮ Open neighborhood locating-dominating in trees ⋮ Locating-dominating codes: bounds and extremal cardinalities ⋮ Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori ⋮ The minimum identifying code graphs ⋮ On the size of identifying codes in triangle-free graphs ⋮ Separating codes and traffic monitoring ⋮ Periodicity of identifying codes in strips ⋮ Identifying codes and locating-dominating sets on paths and cycles ⋮ On the identification problems in products of cycles ⋮ The minimum density of an identifying code in the king lattice. ⋮ Identifying codes in the direct product of a complete graph and some special graphs ⋮ Discriminating codes in (bipartite) planar graphs ⋮ On the number of optimal identifying codes in a twin-free graph ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Centroidal localization game ⋮ Identifying codes of cycles with odd orders ⋮ Maximum size of a minimum watching system and the graphs achieving the bound ⋮ New bounds on binary identifying codes ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Information retrieval and the average number of input clues ⋮ Progress on the description of identifying code polyhedra for some families of split graphs ⋮ Polyhedra associated with identifying codes in graphs ⋮ Operads of finite posets ⋮ On the minimum size of an identifying code over all orientations of a graph ⋮ Adaptive identification in graphs ⋮ Extension of universal cycles for globally identifying colorings of cycles ⋮ Identifying codes for infinite triangular grids with a finite number of rows ⋮ Bounds on the identifying codes in trees ⋮ On a conjecture regarding identification in Hamming graphs ⋮ Improved bounds on identifying codes in binary Hamming spaces ⋮ New identifying codes in the binary Hamming space ⋮ On identifying codes in binary Hamming spaces ⋮ On binary linear \(r\)-identifying codes ⋮ Minimal identifying codes in trees and planar graphs with large girth ⋮ 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 ⋮ Simultaneous resolvability in families of corona product graphs ⋮ Various bounds for liar's domination number ⋮ Strong identification codes for graphs ⋮ Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code ⋮ Characterizing extremal graphs for open neighbourhood location-domination ⋮ Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs ⋮ Upper bounds for binary identifying codes ⋮ Locating and identifying codes in dihedral graphs ⋮ On \(r\)-locating-dominating sets in paths ⋮ On the size of identifying codes in binary hypercubes ⋮ On identifying codes in the hexagonal mesh ⋮ Improved lower bound for locating-dominating codes in binary Hamming spaces ⋮ Combinatorial identification problems and graph powers ⋮ On identification in the triangular grid ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs ⋮ Liar's domination in graphs ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs ⋮ Bounding the trace function of a hypergraph with applications ⋮ Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs ⋮ On the density of identifying codes in the square lattice

This page was built for publication: On a new class of codes for identifying vertices in graphs