Density of identifying codes of hexagonal grids with finite number of rows

¹ Depto de Computação, Universidade Federal do Ceará (UFC), Fortaleza, CE, Brazil
² Instituto de Matemática e Estatstica, Universidade de São Paulo, São Paulo, SP, Brazil

^* Corresponding author: rudini@dc.ufc.br

Received: 2 March 2023
Accepted: 15 February 2024

Abstract

In a graph G, a set C ⊆ V (G) is an identifying code if, for all vertices v in G, the sets N[v] ∩ C are all nonempty and pairwise distinct, where N[v] denotes the closed neighbourhood of v. We focus on the minimum density of identifying codes of infinite hexagonal grids H_k with k rows, denoted by d^*(H_k), and present optimal solutions for k ≤ 5. Using the discharging method, we also prove a lower bound in terms of maximum degree for the minimum-density identifying codes of well-behaved infinite graphs. We prove that d^*(H₂) = 9/20, d^*(H₃) = 6/13 ≈ 0.4615, d^*(H₄) = 7/16 = 0.4375 and d^*(H₅) = 11/25 = 0.44. We also prove that H₂ has a unique periodic identifying code with minimum density.