Advanced Search
Article Contents
Article Contents

Identifying codes of degree 4 Cayley graphs over Abelian groups

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 94B25, 94C12; Secondary: 05C69.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


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


    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.


    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.


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


    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.


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


    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.


    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.


    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-306.doi: 10.1006/jctb.2001.2106.


    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.


    A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs, available at http://www.infres.enst.fr/~lobstein/debutBIBidetlocdom.pdf


    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.


    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.


    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.


    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.


    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.


    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.


    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.

  • 加载中

Article Metrics

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

Access History



    DownLoad:  Full-Size Img  PowerPoint