Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows - Sampaio, Rudini; Sobral, Gabriel A. G.; Wakabayashi, Yoshiko (Anais do Encontro de Teoria da Computação (ETC), 2022)
An identifying code (id code, for short) of a graph is a dominating set such that all vertices have a distinct closed neighbourhood within the code. We present a lower bound for the minimum density of id codes of infinite hexagonal grids with a finite number of rows. We also show that every id code that does not induce a trivial component has density at least 3/7. Finally, we show that when such grids have two rows this minimum density is precisely 9/20. The results on lower bounds are proved using the discharging method.