Minimum Density of Identifying Codes of Hexagonal Grids with a Finite Number of Rows
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.
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.