Lattice-Like Total Perfect Codes

• Autorzy: Carlos Araujo , Italo Dejter
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

perfect dominating sets; hypercubes; lattices

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 1
• Strony: 57-74

Daty

wydano

2014-02-01

online

2014-02-14

Twórcy

autor

Carlos Araujo

• Universidad del Atlántico Barranquilla, Colombia

autor

Italo Dejter

• University of Puerto Rico Rio Piedras, PR 00936-8377

Bibliografia

• [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] 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.
• [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]
• [4] I.J. Dejter and A.A. Delgado, Perfect domination in rectangular grid graphs, J. Combin. Math. Combin. Comput. 70 (2009) 177-196.
• [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]
• [6] I.J. Dejter and P. Weichsel, Twisted perfect dominating subgraphs of hypercubes, Congr. Numer. 94 (1993) 67-78.
• [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] 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]
• [9] D. Hickerson and S. Stein, Abelian groups and packings by semicrosses, Pacific J. Math. 122 (1986) 96-109. doi:10.1137/0118025[Crossref]
• [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]
• [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] W.F. Klostermeyer and J.L. Goldwasser, Total perfect codes in grid graphs, Bull. Inst. Combin. Appl. 46 (2006) 61-68.
• [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] E. Molnár, Sui Mosaici dello spazio de dimensione n, Atti Accad. Naz. Lincei, Rend. Cl. Sci.Fis. Mat Nat. 51 (1971) 177-185.
• [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] 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] S. Stein, Factoring by subsets, Pacific J. Math. 22 (1967) 523-541. doi:10.2140/pjm.1967.22.523[Crossref]
• [18] S. Szabó, On mosaics consisting of mutidimensional crosses, Acta Math. Acad. Sci. Hung. 38 (1981) 191-203. doi:10.1007/BF01917533[Crossref]
• [19] P.M. Weichsel, Dominating sets of n-cubes, J. Graph Theory 18 (1994) 479-488. doi:10.1002/jgt.3190180506 [Crossref]

Identyfikatory

DOI

10.7151/dmgt.1715