×

Optimal identifying codes of two families of Cayley graphs. (English) Zbl 1495.05127

Summary: An identifying code of a graph \(\varGamma\) is a subset \(C\) of the vertex set \(V\) such that for each \(x \in V\), the intersection of its closed neighbourhood with \(C\) is nonempty and unique. If \(\varGamma\) is a finite graph, the density of an identifying code \(C\) is defined as \(\frac{| C |}{| V |}\), which naturally extends to a definition of density in certain infinite graphs which are locally finite. Denote by \(d^\ast (\varGamma)\) the infimum of the density of an identifying code of a finite or infinite graph \(\varGamma\). In this paper, we study identifying codes of an infinite Cayley graph \(\varGamma_n\), which is the Cartesian product of an infinite path and a complete graph on \(n\) vertices. We prove that \(d^\ast (\varGamma_3) = \frac{5}{12}\), \(d^\ast (\varGamma_4) = \frac{9}{22}\) and \(d^\ast (\varGamma_n) = \frac{n - 1}{2 n}\) for \(n \geq 5\). As an application, we obtain \(d^\ast (\varGamma)\) if \(\varGamma\) is a connected quintic Cayley graph over a generalized quaternion group.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C63 Infinite graphs
94B99 Theory of error-correcting codes and error-detecting codes
Full Text: DOI

References:

[1] Ben-Haim, Y.; Litsyn, S., Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math., 19, 69-82 (2005) · Zbl 1085.94026
[2] Bertrand, N.; Charon, I.; Hudry, O.; Lobstein, A., Identifying and locating-dominating codes on chains and cycles, European J. Combin., 25, 969-987 (2004) · Zbl 1053.05095
[3] Blass, U.; Honkala, I.; Litsyn, S., On binary codes for identification, J. Combin. Des., 8, 151-156 (2000) · Zbl 1016.94041
[4] Charon, I.; Honkala, I.; Hudry, O.; Lobstein, A., The minimum density of an identifying code in the king lattice, Discrete Math., 276, 95-109 (2004) · Zbl 1037.05018
[5] Chen, C.; Lu, C.; Miao, Z., Identifying codes and locating-dominating sets on paths and cycles, Discrete Appl. Math., 159, 1540-1547 (2011) · Zbl 1228.05225
[6] Cohen, G.; Gravier, S.; Honkala, I.; Lobstein, A.; Mollard, M.; Payan, C.; Zémor, G., Improved identifying codes for the grid, Electron. J. Combin., 6, R19 (1999), Comments
[7] Daniel, M.; Gravier, S.; Moncel, J., Identifying codes in some subgraphs of the square lattice, Theoret. Comput. Sci., 319, 411-421 (2004) · Zbl 1047.94019
[8] Dantas, R.; Havet, F.; Sampaio, R. M., Minimum density of identifying codes of king grids, Discrete Math., 341, 2708-2719 (2018) · Zbl 1393.05253
[9] Exoo, G.; Junnila, V.; Laihonen, T.; Ranto, S., Improved bounds on identifying codes in binary Hamming spaces, European J. Combin., 31, 813-827 (2010) · Zbl 1196.94094
[10] Feng, M.; Wang, K., Identifying codes of corona product graphs, Discrete Appl. Math., 169, 88-96 (2014) · Zbl 1288.05213
[11] Feng, M.; Xu, M.; Wang, K., Identifying codes of lexicographic product of graphs, Electron. J. Combin., 19, 56-63 (2012) · Zbl 1264.94119
[12] Goddard, W.; Wash, K., ID codes in Cartesian products of cliques, J. Combin. Math. Combin. Comput., 85, 97-106 (2013) · Zbl 1274.05408
[13] Gravier, S.; Moncel, J.; Semri, A., Identifying codes of cycles, European J. Combin., 27, 767-776 (2006) · Zbl 1089.94045
[14] Gravier, S.; Moncel, J.; Semri, A., Identifying codes of Cartesian product of two cliques of the same size, Electron. J. Combin., 15, N4 (2008) · Zbl 1180.05088
[15] M.C. Heydemann, Cayley graphs and interconnection networks, in: G. Hahn (Ed.), Graph Symmetry: Algebraic Methods and Applications, Kluwer, Montreal, 1997, pp. 167-224. · Zbl 0885.05075
[16] Honkala, I., An optimal strongly identifying code in the infinite triangular grid, Electron. J. Combin., 17, R91 (2010) · Zbl 1193.05125
[17] Honkala, I.; Laihonen, T., On identifying codes in the triangular and square grids, SIAM J. Comput., 33, 304-312 (2004) · Zbl 1060.94053
[18] Honkala, I.; Lobstein, A., On identifying codes in binary hamming spaces, J. Combin. Theory Ser. A, 99, 232-243 (2002) · Zbl 1005.94030
[19] Janson, S.; Laihonen, T., On the size of identifying codes in binary hypercubes, J. Combin. Theory Ser. A, 116, 1087-1096 (2009) · Zbl 1173.94009
[20] Junnila, V.; Laihonen, T., Optimal identifying codes in cycles and paths, Graphs Combin., 28, 469-481 (2012) · Zbl 1256.05124
[21] Karpovsky, M. G.; Chakrabarty, K.; Levitin, L. B., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44, 599-611 (1998) · Zbl 1105.94342
[22] Kim, J. L.; Kim, S. J., Identifying codes in \(q\)-ary hypercubes, Bull. Inst. Combin. Appl., 59, 93-102 (2010) · Zbl 1216.94063
[23] Lu, M.; Xu, J.; Zhang, Y., Identifying codes in the direct product of a complete graph and some special graphs, Discrete Appl. Math., 254, 175-182 (2019) · Zbl 1404.05182
[24] Moncel, J., Monotonicity of the minimum cardinality of an identifying code in the hypercube, Discrete Appl. Math., 154, 898-899 (2006) · Zbl 1093.94033
[25] Pelto, M., The number of completely different optimal identifying codes in the infinite square grid, Discrete Appl. Math., 233, 143-158 (2017) · Zbl 1403.94129
[26] Rall, D. F.; Wash, K., Identifying codes of the direct product of two cliques, European J. Combin., 36, 159-171 (2014) · Zbl 1284.05200
[27] Rall, D. F.; Wash, K., On minimum identifying codes in some Cartesian product graphs, Graphs Combin., 33, 1037-1053 (2017) · Zbl 1371.05220
[28] Rosendahl, P., On the identification problems in products of cycles, Discrete Math., 275, 277-288 (2004) · Zbl 1030.05098
[29] Song, S.; Ning, X.; Cheng, P., Locating and identifying codes in dihedral graphs, Appl. Math. Comput., 416, Article 126752 pp. (2022) · Zbl 1510.05236
[30] Stanton, B., Vertex identifying codes for the \(n\)-dimensional lattice, Australas. J. Combin., 53, 299-307 (2012) · Zbl 1261.94040
[31] L. Tang, L. Feng, W. Liu, X. Ma, Location and identification domination number of Cayley graphs over dicyclic groups, submitted for publication.
[32] Xu, M.; Thulasiraman, K.; Hu, X., Identifying codes of cycles with odd orders, European J. Combin., 29, 1717-1720 (2008) · Zbl 1145.94020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.