May  2015, 9(2): 129-148. doi: 10.3934/amc.2015.9.129

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, Spain, Spain, Spain

Received  June 2012 Published  May 2015

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.
Citation: Cristóbal Camarero, Carmen Martínez, Ramón Beivide. Identifying codes of degree 4 Cayley graphs over Abelian groups. Advances in Mathematics of Communications, 2015, 9 (2) : 129-148. doi: 10.3934/amc.2015.9.129
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.  doi: 10.1109/12.93744.  Google Scholar

[2]

Y. Ben-Haim, S. Gravier, A. Lobstein and J. Moncel, Adaptive identification in graphs,, J. Comb. Theory Ser. A, 115 (2008), 1114.  doi: 10.1016/j.jcta.2007.12.009.  Google Scholar

[3]

Y. Ben-Haim, S. Gravier, A. Lobstein and J. Moncel, Adaptive identification in Torii in the King lattice,, Electr. J. Combin., 18 (2011).   Google Scholar

[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.  doi: 10.1137/S0895480104444089.  Google Scholar

[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.  doi: 10.1016/0095-8956(89)90040-3.  Google Scholar

[6]

C. Camarero and C. Martíez and R. Beivide, Identifying codes over L-graphs,, in 3th Int. Castle Meeting Coding Theory Appl., (2011).   Google Scholar

[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).   Google Scholar

[8]

I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs,, Electr. J. Combin., 9 (2002).   Google Scholar

[9]

M. A. Fiol, On congruence in $\mathbb Z^n$ and the dimension of a multidimensional circulant,, Discrete Math., 141 (1995), 1.  doi: 10.1016/0012-365X(94)00361-L.  Google Scholar

[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.  doi: 10.1109/TC.1987.1676963.  Google Scholar

[11]

J. H. Jordan and C. J. Potratz, Complete residue systems in the Gaussian integers,, Math. Magazine, 38 (1965), 1.   Google Scholar

[12]

I. Honkala and A. Lobstein, On the density of identifying codes in the square lattice,, J. Comb. Theory Ser. B, 85 (2002), 297.  doi: 10.1006/jctb.2001.2106.  Google Scholar

[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.  doi: 10.1109/18.661507.  Google Scholar

[14]

A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs,, available at , ().   Google Scholar

[15]

M. Malek, A comparison connection assignment for diagnosis of multiprocessor systems,, in Proc. 7th Annual Symp. Comput. Arch., (1980), 31.  doi: 10.1145/800053.801906.  Google Scholar

[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.  doi: 10.1109/TC.2008.57.  Google Scholar

[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.  doi: 10.1109/ISIT.2010.5513724.  Google Scholar

[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.  doi: 10.1109/PGEC.1967.264748.  Google Scholar

[19]

C. H. Sequin, Doubly twisted torus networks for VLSI processor arrays,, in Proc. 8th Annual Symp. Comput. Arch., (1981), 471.   Google Scholar

[20]

C. K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organizations,, J. ACM, 21 (1974), 392.  doi: 10.1145/321832.321838.  Google Scholar

[21]

J. Zerovnik, Perfect codes in direct product of cycles - a complete characterization,, Adv. Appl. Math., 41 (2008), 197.  doi: 10.1016/j.aam.2007.04.006.  Google Scholar

show all references

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.  doi: 10.1109/12.93744.  Google Scholar

[2]

Y. Ben-Haim, S. Gravier, A. Lobstein and J. Moncel, Adaptive identification in graphs,, J. Comb. Theory Ser. A, 115 (2008), 1114.  doi: 10.1016/j.jcta.2007.12.009.  Google Scholar

[3]

Y. Ben-Haim, S. Gravier, A. Lobstein and J. Moncel, Adaptive identification in Torii in the King lattice,, Electr. J. Combin., 18 (2011).   Google Scholar

[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.  doi: 10.1137/S0895480104444089.  Google Scholar

[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.  doi: 10.1016/0095-8956(89)90040-3.  Google Scholar

[6]

C. Camarero and C. Martíez and R. Beivide, Identifying codes over L-graphs,, in 3th Int. Castle Meeting Coding Theory Appl., (2011).   Google Scholar

[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).   Google Scholar

[8]

I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs,, Electr. J. Combin., 9 (2002).   Google Scholar

[9]

M. A. Fiol, On congruence in $\mathbb Z^n$ and the dimension of a multidimensional circulant,, Discrete Math., 141 (1995), 1.  doi: 10.1016/0012-365X(94)00361-L.  Google Scholar

[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.  doi: 10.1109/TC.1987.1676963.  Google Scholar

[11]

J. H. Jordan and C. J. Potratz, Complete residue systems in the Gaussian integers,, Math. Magazine, 38 (1965), 1.   Google Scholar

[12]

I. Honkala and A. Lobstein, On the density of identifying codes in the square lattice,, J. Comb. Theory Ser. B, 85 (2002), 297.  doi: 10.1006/jctb.2001.2106.  Google Scholar

[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.  doi: 10.1109/18.661507.  Google Scholar

[14]

A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs,, available at , ().   Google Scholar

[15]

M. Malek, A comparison connection assignment for diagnosis of multiprocessor systems,, in Proc. 7th Annual Symp. Comput. Arch., (1980), 31.  doi: 10.1145/800053.801906.  Google Scholar

[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.  doi: 10.1109/TC.2008.57.  Google Scholar

[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.  doi: 10.1109/ISIT.2010.5513724.  Google Scholar

[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.  doi: 10.1109/PGEC.1967.264748.  Google Scholar

[19]

C. H. Sequin, Doubly twisted torus networks for VLSI processor arrays,, in Proc. 8th Annual Symp. Comput. Arch., (1981), 471.   Google Scholar

[20]

C. K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organizations,, J. ACM, 21 (1974), 392.  doi: 10.1145/321832.321838.  Google Scholar

[21]

J. Zerovnik, Perfect codes in direct product of cycles - a complete characterization,, Adv. Appl. Math., 41 (2008), 197.  doi: 10.1016/j.aam.2007.04.006.  Google Scholar

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (49)
  • HTML views (0)
  • Cited by (1)

[Back to Top]