Bounds for codes identifying vertices in the hexagonal grid

DOI10.1137/S0895480199360990MaRDI QIDQ2706181zbMATH OpenFDO

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

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480199360990

zbMATH Keywords

densityhexagonal grididentifying codenonempty and different from

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Bounds on codes (94B65)

Review text

In an undirected graph \(G=(V,E)\), a subset \(C\) of \(V\) is called an identifying code of the sets \(B_1(v)\cap C\) consisting of all elements of \(C\) within distance one from the vertex \(v\) if these sets are nonempty and different. The authors take as \(G\) the infinite hexagonal grid graph and show that the density of any identifying code is at least \(16/39\) and that there is an identifying code of density \(3/7\).

Recommendations

• A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
• New bounds on the minimum density of an identifying code for the infinite hexagonal grid
• New bounds for codes identifying vertices in graphs
• Lower bounds for identifying codes in some infinite grids
• Improved Bounds forr-Identifying Codes of the Hex Grid

Cited in

(36)

• On identifying codes in the hexagonal mesh
• New bounds for codes identifying vertices in graphs
• Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
• The minimum density of an identifying code in the king lattice.
• Paths and cycles identifying vertices in twisted cubes
• On identification in the triangular grid
• On the density of identifying codes in the square lattice
• Optimal open-locating-dominating sets in infinite triangular grids
• On identifying codes that are robust against edge changes
• Watching systems in the King grid
• A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
• Completely regular codes in the infinite hexagonal grid
• An improved lower bound for \((1,\leq 2)\)-identifying codes in the king 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
• Liar's domination
• Improved Bounds forr-Identifying Codes of the Hex Grid
• Locating-domination and identification
• Optimal lower bound for 2-identifying codes in the hexagonal grid
• Open-independent, open-locating-dominating sets
• Identifying codes for infinite triangular grids with a finite number of rows
• 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 and locating-dominating sets on paths and cycles
• Density of identifying codes of hexagonal grids with finite number of rows
• On Iiro Honkala's contributions to identifying codes
• Finding codes on infinite grids automatically
• Optimal local identifying and local locating-dominating codes
• Optimal error-detection system for identifying codes
• Fault-tolerant identifying codes in special classes of graphs
• On (1, l)-locating-dominating codes in infinite triangular grid
• On a new class of identifying codes in graphs
• On robust identification in the square and King grids
• Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice
• Fault tolerant detectors for distinguishing sets in graphs

This page was built for publication: Bounds for codes identifying vertices in the hexagonal grid

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