New bounds on the minimum density of an identifying code for the infinite hexagonal grid

DOI10.1016/J.DAM.2013.06.002MaRDI QIDQ2446882zbMATH OpenOpenAlexFDO

Authors Ari Cukierman, Gexin Yu

Publication date 23 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.1097

zbMATH Keywords

discharging methodidentifying codeinfinite hexagonal grid

Mathematics Subject Classification ID

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

Abstract: For a graph, $G$, and a vertex $vinV(G)$, let $N[v]$ be the set of vertices adjacent to and including $v$. A set $DsubseteqV(G)$ is a vertex identifying code if for any two distinct vertices $v_1,v_{2}inV(G)$, the vertex sets $N[v_1]capD$ and $N[v_2]capD$ are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of $3/7approx0.428571$, and this remains the best known upper bound. Until now, the best known lower bound was $12/29approx0.413793$ and was proved by Cranston and Yu in 2009. We present three new codes with a density of 3/7, and we improve the lower bound to $5/12approx0.416667$.

Recommendations

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

Cites work

• A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
• Bounds for codes identifying vertices in the hexagonal grid
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Identification in \(\mathbb Z^2\) using Euclidean balls
• Improved Bounds forr-Identifying Codes of the Hex Grid
• Lower bounds for identifying codes in some infinite grids
• On a new class of codes for identifying vertices in graphs
• Optimal lower bound for 2-identifying codes in the hexagonal grid

Cited in

(28)

• On identifying codes in the hexagonal mesh
• Operads of finite posets
• On the minimum size of an identifying code over all orientations of a graph
• Lower bounds for identifying codes in some infinite grids
• Open locating-dominating sets in circulant graphs
• Optimal open-locating-dominating sets in infinite triangular grids
• A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
• New bounds for (\(r, \leq 2\))-identifying codes in the infinite king grid
• Completely regular codes in the infinite hexagonal grid
• New lower bound for 2-identifying code in the square grid
• Bounds for codes identifying vertices in the hexagonal grid
• Minimum-Density Identifying Codes in Square Grids
• 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
• 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
• Fault tolerant detectors for distinguishing sets in graphs
• An optimal strongly identifying code in the infinite triangular grid

This page was built for publication: New bounds on the minimum density of an identifying code for the infinite hexagonal grid

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