Identifying codes of degree 4 Cayley graphs over Abelian groups

Cristóbal  Camarero; Carmen  Martínez; Ramón  Beivide

doi:10.3934/amc.2015.9.129

Article Contents

2015, Volume 9, Issue 2: 129-148. Doi: 10.3934/amc.2015.9.129

This issue Previous Article Next Article Information--bit error rate and false positives in an MDS code

Identifying codes of degree 4 Cayley graphs over Abelian groups

1.
Computer Science and Electronics Department of the University of Cantabria, Faculty of Sciences, Avenida de los Castros s/n, 39005 Santander

Received: June 2012

Published: May 2015

Abstract / Introduction Related Papers Cited by

Abstract

In this paper a wide family of identifying codes over regular Cayley graphs of degree four which are built over finite Abelian groups is presented. Some of the codes in this construction are also perfect. The graphs considered include some well-known graphs such as tori, twisted tori and Kronecker products of two cycles. Therefore, the codes can be used for identification in these graphs. Finally, an example of how these codes can be applied for adaptive identification over these graphs is presented.

Keywords:

Mathematics Subject Classification: Primary: 94B25, 94C12; Secondary: 05C69.

Citation:

Related Papers

Cited by

References

[1]	R. Beivide, E. Herrada, J. L. Balcázar and A. Arruabarrena, Optimal distance networks of low degree for parallel computers, IEEE Trans. Comput., 40 (1991), 1109-1124.doi: 10.1109/12.93744.
[2]	Y. Ben-Haim, S. Gravier, A. Lobstein and J. Moncel, Adaptive identification in graphs, J. Comb. Theory Ser. A, 115 (2008), 1114-1126.doi: 10.1016/j.jcta.2007.12.009.
[3]	Y. Ben-Haim, S. Gravier, A. Lobstein and J. Moncel, Adaptive identification in Torii in the King lattice, Electr. J. Combin., 18 (2011), #P116.
[4]	Y. Ben-Haim and S. Litsyn, Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math., 19 (2005), 69-82.doi: 10.1137/S0895480104444089.
[5]	J.-C. Bermond, O. Favaron and M. Maheo, Hamiltonian decomposition of Cayley graphs of degree 4, J. Comb. Theory Ser. B, 46 (1989), 142-153.doi: 10.1016/0095-8956(89)90040-3.
[6]	C. Camarero and C. Martíez and R. Beivide, Identifying codes over L-graphs, in 3th Int. Castle Meeting Coding Theory Appl., Barcelona, 2011.
[7]	I. Charon, I. Honkala, O. Hudry and A. Lobstein, General bounds for identifying codes in some infinite regular graphs, Electr. J. Combin., 8 (2001), #R39.
[8]	I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs, Electr. J. Combin., 9 (2002), #R11.
[9]	M. A. Fiol, On congruence in $\mathbb Z^n$ and the dimension of a multidimensional circulant, Discrete Math., 141 (1995), 1-3.doi: 10.1016/0012-365X(94)00361-L.
[10]	M. A. Fiol, J. L. Yebra, I. Alegre and M. Valero, Discrete optimization problem in local networks and data alignment, IEEE Trans. Comput., 36 (1987), 702-713.doi: 10.1109/TC.1987.1676963.
[11]	J. H. Jordan and C. J. Potratz, Complete residue systems in the Gaussian integers, Math. Magazine, 38 (1965), 1-12.
[12]	I. Honkala and A. Lobstein, On the density of identifying codes in the square lattice, J. Comb. Theory Ser. B, 85 (2002), 297-306.doi: 10.1006/jctb.2001.2106.
[13]	M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory, 44 (1998), 599-611.doi: 10.1109/18.661507.
[14]	A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs, available at http://www.infres.enst.fr/~lobstein/debutBIBidetlocdom.pdf
[15]	M. Malek, A comparison connection assignment for diagnosis of multiprocessor systems, in Proc. 7th Annual Symp. Comput. Arch., ACM, New York, 1980, 31-36.doi: 10.1145/800053.801906.
[16]	C. Martínez, R. Beivide, E. Stafford, M. Moreto and E. M. Gabidulin, Modeling toroidal networks with the Gaussian integers, IEEE Trans. Comput., 57 (2008), 1046-1056.doi: 10.1109/TC.2008.57.
[17]	C. Martínez, C. Camarero and R. Beivide, Perfect graph codes over two dimensional lattices, in 2010 IEEE Int. Symp. Inform. Theory, 2010, 1047-1051.doi: 10.1109/ISIT.2010.5513724.
[18]	F. P. Preparata, G. Metze and R. T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Electr. Comput., EC-16 (1967), 848-854.doi: 10.1109/PGEC.1967.264748.
[19]	C. H. Sequin, Doubly twisted torus networks for VLSI processor arrays, in Proc. 8th Annual Symp. Comput. Arch., IEEE Comput. Soc. Press, 1981, 471-480.
[20]	C. K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organizations, J. ACM, 21 (1974), 392-402.doi: 10.1145/321832.321838.
[21]	J. Zerovnik, Perfect codes in direct product of cycles - a complete characterization, Adv. Appl. Math., 41 (2008), 197-205.doi: 10.1016/j.aam.2007.04.006.