Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows
Resumo
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.
Palavras-chave:
Discharging Method, Hexagonal Grid, Identifying Codes
Referências
Charon, I., Hudry, O., and Lobstein, A. (2003). Minimizing the size of an identifying or locating-dominating code in a graph is np-hard. Theoretical Computer Scienc, 290:2109–2120.
Cohen, G. D., Honkala, I., Lobstein, A., and Zémor, G. (2000). Bounds for codes identifying vertices in the hexagonal grid. SIAM J. on Discrete Mathematics, pages 492–504.
Cranston, D. W. and West, D. B. (2017). An introduction to the discharging method via graph coloring. Discrete Mathematics, 340:766–793.
Cranston, D. W. and Yu, G. (2009). A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid. The Elect. J. of Combinatorics, 16:R113.
Cukierman, A. and Yu, G. (2013). New bounds on the minimum density of an identifying code for the infinite hexagonal grid. Discrete Applied Mathematics, 161:2910–2924.
Karpovsky, M. G., Chakrabarty, K., and Levitin, L. B. (1998). On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, 44:599–611.
Lobstein, A. (2021). Watching systems, identifying, locating-dominating and discriminating codes in graphs. https://www.lri.fr/~lobstein/debutBIBidetlocdom.pdf. Accessed on: March 1st 2022.
Cohen, G. D., Honkala, I., Lobstein, A., and Zémor, G. (2000). Bounds for codes identifying vertices in the hexagonal grid. SIAM J. on Discrete Mathematics, pages 492–504.
Cranston, D. W. and West, D. B. (2017). An introduction to the discharging method via graph coloring. Discrete Mathematics, 340:766–793.
Cranston, D. W. and Yu, G. (2009). A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid. The Elect. J. of Combinatorics, 16:R113.
Cukierman, A. and Yu, G. (2013). New bounds on the minimum density of an identifying code for the infinite hexagonal grid. Discrete Applied Mathematics, 161:2910–2924.
Karpovsky, M. G., Chakrabarty, K., and Levitin, L. B. (1998). On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, 44:599–611.
Lobstein, A. (2021). Watching systems, identifying, locating-dominating and discriminating codes in graphs. https://www.lri.fr/~lobstein/debutBIBidetlocdom.pdf. Accessed on: March 1st 2022.
Publicado
31/07/2022
Como Citar
SAMPAIO, Rudini; SOBRAL, Gabriel A. G.; WAKABAYASHI, Yoshiko.
Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 145-148.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.223348.
