%A Sampaio, Rudini
%A Sobral, Gabriel A. G.
%A Wakabayashi, Yoshiko
%D 2022
%T Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows
%K
%X 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.
%U https://sol.sbc.org.br/index.php/etc/article/view/20680
%J Anais do Encontro de Teoria da Computação (ETC)
%0 Journal Article
%R 10.5753/etc.2022.223348
%P 145-148%@ 2595-6116
%8 2022-07-31