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.

[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.

[3]

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

[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.

[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.

[6]

C. Camarero and C. Martíez and R. Beivide, Identifying codes over L-graphs,, in 3th Int. Castle Meeting Coding Theory Appl., (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).

[8]

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

[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.

[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.

[11]

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

[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.

[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.

[14]

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

[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.

[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.

[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.

[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.

[19]

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

[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.

[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.

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.

[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.

[3]

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

[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.

[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.

[6]

C. Camarero and C. Martíez and R. Beivide, Identifying codes over L-graphs,, in 3th Int. Castle Meeting Coding Theory Appl., (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).

[8]

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

[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.

[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.

[11]

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

[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.

[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.

[14]

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

[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.

[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.

[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.

[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.

[19]

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

[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.

[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.

[1]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[2]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[3]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[4]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[5]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[6]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013

[7]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[8]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[9]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261

[10]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

[11]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275

[12]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027

[13]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032

[14]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281

[15]

Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z4. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017

[16]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042

[17]

Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503

[18]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129

[19]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17

[20]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

2016 Impact Factor: 0.8

Metrics

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

[Back to Top]