Lattice-Like Total Perfect Codes

Carlos Araujo; Italo Dejter

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 1, page 57-74
  • ISSN: 2083-5892

Abstract

top
A contribution is made to the classification of lattice-like total perfect codes in integer lattices Λn via pairs (G, Φ) formed by abelian groups G and homomorphisms Φ: Zn → G. A conjecture is posed that the cited contribution covers all possible cases. A related conjecture on the unfinished work on open problems on lattice-like perfect dominating sets in Λn with induced components that are parallel paths of length > 1 is posed as well.

How to cite

top

Carlos Araujo, and Italo Dejter. "Lattice-Like Total Perfect Codes." Discussiones Mathematicae Graph Theory 34.1 (2014): 57-74. <http://eudml.org/doc/267791>.

@article{CarlosAraujo2014,
abstract = {A contribution is made to the classification of lattice-like total perfect codes in integer lattices Λn via pairs (G, Φ) formed by abelian groups G and homomorphisms Φ: Zn → G. A conjecture is posed that the cited contribution covers all possible cases. A related conjecture on the unfinished work on open problems on lattice-like perfect dominating sets in Λn with induced components that are parallel paths of length > 1 is posed as well.},
author = {Carlos Araujo, Italo Dejter},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {perfect dominating sets; hypercubes; lattices},
language = {eng},
number = {1},
pages = {57-74},
title = {Lattice-Like Total Perfect Codes},
url = {http://eudml.org/doc/267791},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Carlos Araujo
AU - Italo Dejter
TI - Lattice-Like Total Perfect Codes
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 57
EP - 74
AB - A contribution is made to the classification of lattice-like total perfect codes in integer lattices Λn via pairs (G, Φ) formed by abelian groups G and homomorphisms Φ: Zn → G. A conjecture is posed that the cited contribution covers all possible cases. A related conjecture on the unfinished work on open problems on lattice-like perfect dominating sets in Λn with induced components that are parallel paths of length > 1 is posed as well.
LA - eng
KW - perfect dominating sets; hypercubes; lattices
UR - http://eudml.org/doc/267791
ER -

References

top
  1. [1] C. Araujo, I.J. Dejter and P. Horak, A generalization of Lee codes, Des. Codes Cryptogr., online version, (21 April 2012). doi:10.1007/s10623-012-9666-6[Crossref] 
  2. [2] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, Appl. Discrete Math., R.D. Ringeisen and F.S. Roberts, Eds., SIAM, Philadelphia (1988) 189-199. Zbl0664.05027
  3. [3] S.I. Costa, M. Muniz, E. Agustini, and R. Palazzo, Graphs, tessellations, and perfect codes on flat tori, IEEE Trans. Inform. Theory 50 (2004) 2363-2377. doi:10.1109/TIT.2004.834754[Crossref] Zbl1231.94070
  4. [4] I.J. Dejter and A.A. Delgado, Perfect domination in rectangular grid graphs, J. Combin. Math. Combin. Comput. 70 (2009) 177-196. Zbl1195.05053
  5. [5] I.J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 119 (2003) 319-328. doi:10.1016/S0166-218X(02)00573-5[WoS][Crossref] Zbl1035.05060
  6. [6] I.J. Dejter and P. Weichsel, Twisted perfect dominating subgraphs of hypercubes, Congr. Numer. 94 (1993) 67-78. Zbl0801.05063
  7. [7] T. Etzion, Product constructions for perfect Lee Codes, IEEE Trans. Inform. Theory 57 (2011) 7473-7481. doi:10.1109/TIT.2011.2161133[Crossref][WoS] 
  8. [8] S. Golomb and K.Welch, Perfect codes in Lee metric and the packing of polyominoes, SIAM J. Appl. Math. 18 (1970) 302-317. doi:10.1137/0118025[Crossref] Zbl0192.56302
  9. [9] D. Hickerson and S. Stein, Abelian groups and packings by semicrosses, Pacific J. Math. 122 (1986) 96-109. doi:10.1137/0118025[Crossref] Zbl0549.52009
  10. [10] P. Horak and B.F. AlBdaiwi, Non-periodic tilings of Rn by crosses, Discrete Comput. Geom. 47 (2012) 1-16. doi:10.1007/s00454-011-9373-5[WoS][Crossref] Zbl1241.52008
  11. [11] P. Horak and B.F. AlBdaiwi, Diameter perfect Lee codes, IEEE Trans. Inform. Theory 58 (2012) 5490-5499. doi:10.1109/TIT.2012.2196257[Crossref][WoS] 
  12. [12] W.F. Klostermeyer and J.L. Goldwasser, Total perfect codes in grid graphs, Bull. Inst. Combin. Appl. 46 (2006) 61-68. Zbl1095.05028
  13. [13] J. Kratochvil and M. Kriv´anek, On the computational complexity of codes in graphs, in: Proc. MFCS 1988, LN Comp. Sci. 324 (Springer-Verlag) 396-404. doi:10.1007/BFb0017162[Crossref] 
  14. [14] E. Molnár, Sui Mosaici dello spazio de dimensione n, Atti Accad. Naz. Lincei, Rend. Cl. Sci.Fis. Mat Nat. 51 (1971) 177-185. Zbl0257.05024
  15. [15] M. Schwartz, Quasi-cross lattice tilings with applications to flash memory, IEEE Trans. Inform. Theory 58 (2012) 2397-2405. doi:10.1109/TIT.2011.2176718[WoS][Crossref] 
  16. [16] S. Stein, Packings of Rn by certain error spheres, IEEE Trans. Inform. Theory 30 (1984) 356-363. doi:10.1109/TIT.1984.1056880[Crossref] 
  17. [17] S. Stein, Factoring by subsets, Pacific J. Math. 22 (1967) 523-541. doi:10.2140/pjm.1967.22.523[Crossref] Zbl0149.26501
  18. [18] S. Szabó, On mosaics consisting of mutidimensional crosses, Acta Math. Acad. Sci. Hung. 38 (1981) 191-203. doi:10.1007/BF01917533[Crossref] Zbl0477.20029
  19. [19] P.M. Weichsel, Dominating sets of n-cubes, J. Graph Theory 18 (1994) 479-488. doi:10.1002/jgt.3190180506 [Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.