New bounds for codes identifying vertices in graphs

MaRDI QIDQ1283874zbMATH OpenFDO

Authors Iiro Honkala, Gilles Zémor, Gérard Cohen, Antoine Lobstein

Publication date 31 March 1999

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119827, http://www.emis.de/journals/EJC/Volume_6/v6i1toc.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

codeinfinite graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Theory of error-correcting codes and error-detecting codes (94B99) Fault detection; testing in circuits and networks (94C12)

Review text

Suppose \(G\) is an undirected graph and \(C\) a subset of the vertices of \(G\) which is called a code. For any vertex \(v\) of \(G\), the neighboring set is the set of vertices in \(C\) at a distance at most 1 from \(v\). The code \(C\) is said to identify the vertices of \(G\) if the neighboring sets are all nonempty and different. The authors consider \(G\) a square grid drawn on a torus and establish the minimum density \(D\) of an identifying code of the limiting infinite graph as \(23/66\leq D\leq 5/14\).

Recommendations

• Bounds for codes identifying vertices in the hexagonal grid
• Lower bounds for identifying codes in some infinite grids
• On the density of identifying codes in the square lattice
• Minimum-Density Identifying Codes in Square Grids
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid

Cited in

(32)

• The minimum density of an identifying code in the king lattice.
• On strongly identifying codes
• Periodicity of identifying codes in strips
• On identification in the triangular grid
• On the density of identifying codes in the square lattice
• On the identification of vertices using cycles
• Neighborhood distinguishing coloring in graphs
• Identifying codes in the complementary prism of cycles
• Improved upper bounds for identifying codes in n-dimensional q-ary cubes
• Sphere coverings and identifying codes
• Locating and identifying codes in circulant networks
• Locating sensors in paths and cycles: the case of 2-identifying codes
• Bounds on codes derived by counting components in Varshamov graphs
• An unexpected result in coding the vertices of a graph
• Bounds for codes identifying vertices in the hexagonal grid
• Minimum-Density Identifying Codes in Square Grids
• Vertex identifying codes for the n-dimensional lattice
• Complexity results for identifying codes in planar graphs
• Liar's domination
• On codes identifying vertices in the two-dimensional square lattice with diagonals
• Identifying codes for infinite triangular grids with a finite number of rows
• On Optimal Edge-Robust and Vertex-Robust $(1,\leq l)$-Identifying Codes
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Minimum density of identifying codes of king grids
• Minimum density of identifying codes of king grids
• General bounds for identifying codes in some infinite regular graphs
• Identifying codes in some subgraphs of the square lattice
• Identifying codes for generalized quadrangles
• Open neighborhood locating-dominating in trees
• On a new class of identifying codes in graphs
• On robust identification in the square and King grids
• On graphs having a \(V\setminus \{x\}\) set as an identifying code

This page was built for publication: New bounds for codes identifying vertices in graphs

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