TY - JOUR
AU - Sampaio, Rudini
AU - Sobral, Gabriel A. G.
AU - Wakabayashi, Yoshiko
PY - 2022/07/31
TI - Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows
JF - Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.223348
KW -
N2 - 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.
UR - https://sol.sbc.org.br/index.php/etc/article/view/20680