Quasi perfect codes in the cartesian product of some graphs

Smruti Mane, Neeta Shinde

Abstract


An important question in the study of quasi-perfect codes is whether such codes can be constructed for all possible lengths n. In this paper, we address this question for specific values of n. First, we investigate the existence of quasi-perfect codes in the Cartesian product of a graph G and a path (or cycle), assuming that G admits a perfect code. Second, we explore quasi-perfect codes in the Cartesian products of two or three cycles, Cm□Cn and Cm□Cn□Cl, as well as in the Cartesian products of two or three paths, Pm□Pn and Pm□Pn□Pl.

Keywords


graph; quasi-perfect code; Cartesian product; cycle; path; mesh

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2025.13.2.14

References

B. AlBdaiwi and P. Horak, Perfect distance-d placements in 3-dimensional tori, J. Combinat. Math. Combinat. Comput. 43 (2002), 159–174.

B. AlBdaiwi and B. Bose, Quasi-perfect Lee distance codes, IEEE Trans. Inf. Theory 49 (6) (2003), 1535–1539.

B. AlBdaiwi and M. Livingston, Perfect distance-d placements in 2-dimensional tori, J. Supercomput. 29 (1) (2004), 45–57.

B. AlBdaiwi and B. Bose, Quasi-perfect resource placements for two-dimensional toroidal networks, J. Parallel Distrib. Comput. 65 (2005), 815–831.

B. AlBdaiwi, P. Horak, and L. Milazzo, Enumerating and decoding perfect linear Lee codes, Designs, Codes Cryptogr. 52 (2) (2009), 155–162.

T. Baicheva, I. Bouyukliev, S. Dodunekov, and V. Fack, Binary and Ternary Linear Quasi-Perfect Codes With Small Dimensions, IEEE Trans. Inform. Theory 54 (9) (2008), 4335–4339.

K. Bibak, B. Kapron, and V. Srinivasan, The Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs, IEEE Trans. Inf. Theory 62 (11) (2016), 6355–6358.

R. Brualdi, V. Pless, and R. Wilson, Short codes with a given covering radius, IEEE Trans. Inf. Theory 35 (1) (1989), 99–109.

S. Buzaglo and T. Etzion, Tilings by (0.5, n)-crosses and perfect codes, SIAM J. Discrete Math. 27 (2) (2013), 1067–1081.

C. Camarero and C. Martínez, Quasi-perfect Lee codes of radius 2 and arbitrarily large dimension, IEEE Trans. Inf. Theory 62 (3) (2016), 1183–1192.

D. Danev and S. Dodunekov, A family of ternary quasi-perfect BCH codes, Des. Codes Cryptogr. 49 (1-3) (2008), 265–271.

A. Davydov and A. Drozhzhina-Labinskaya, Constructions, families, and tables of binary linear covering codes, IEEE Trans. Inf. Theory 40 (4) (1994), 1270–1279.

A. Davydov and L. Tombak, Quasi-perfect linear binary codes with distance 4 and complete caps in projective geometry, Probl. Inf. Transm. 25 (4) (1989), 265–275.

T. Etzion and G. Greenberg, Constructions for perfect mixed codes and other covering codes, IEEE Trans. Inf. Theory 39 (1) (1993), 209–214.

T. Etzion and B. Mounits, Quasi-perfect codes with small distance, IEEE Trans. Inform. Theory 51 (11) (2005), 3928–3946.

E. Gabidulin, A. Davydov, and L. Tombak, Linear codes with covering radius 2 and other new covering codes, IEEE Trans. Inf. Theory 37 (1) (1991), 219–224.

S. Golomb and L. Welch, Perfect codes in the Lee metric and the packing of polyominoes, SIAM J. Appl. Math. 18 (2) (1970), 302–317.

D. Gorenstein, W. Peterson, and N. Zierler, Two-error correcting Bose-Chaudhuri codes are quasi-perfect, Inf. Contr. 3 (1960), 291–294.

P. Horak and B. AlBdaiwi, Fast decoding of quasi-perfect Lee distance codes, Designs, Codes Cryptogr. 40 (3) (2006), 357–367.

P. Horak and B. AlBdaiwi, Non-periodic tilings of Rn by crosses, Discrete Comput. Geometry 47 (1) (2012), 1–16.

P. Horak and V. Hromada, Tiling R5 by crosses, Discrete Comput. Geometry 51 (2) (2014), 269–284.

P. Horak and O. Grošek, A new approach towards the Golomb–Welch conjecture, Eur. J. Combinat. 38 (2014), 12–22.

C. Lee, Some properties of nonbinary error-correcting codes, IRE Trans. Inf. Theory IT-4 (2) (1958), 77–82.

M. Livingston and Q. Stout, Perfect dominating sets, Congr. Numer. 79 (1990), 187–203.

O. Moreno, Further results on quasi-perfect codes related to the Goppa codes, Congressus Numerantium 40 (1983), 249–256.

C. Queiroz, C. Camarero, C. Martínez, and R. Palazzo, Jr., Quasi-perfect codes from Cayley graphs over integer rings, IEEE Trans. Inf. Theory 59 (9) (2013), 5905–5916.

J. Strapasson, G. Jorge, A. Campello, and S. Costa, Quasi-perfect codes in the lp metric, Comp. Appl. Math. 37 (2018), 852–866.

R. Struik, Covering Codes, Ph.D. dissertation, Eindhoven Univ. Technol., Eindhoven, The Netherlands, 1994.

S. Szabó, On mosaics consisting of multidimensional crosses, Acta Math. Acad. Sci. Hung. 38 (1–4) (1981), 191–203.

T. Wagner, A search technique for quasi-perfect codes, Inf. Contr. 9 (1966), 94–99.

D. West, Introduction to Graph Theory, 2nd ed., Prentice Hall of India, New Delhi, 2002.

G. Zaitsev, V. Zinovjev, and N. Semakov, Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-error-correcting codes, in Proc. 2nd Int. Symp. Information Theory, B. N. Petrov and F. Csáki, Eds. Budapest, Hungary: Akadémiai Kiadó, 1973, pp. 257–263.

T. Zhang and G. Ge, Perfect and quasi-perfect codes under the lp metric, IEEE Trans. Inf. Theory, 63 (7) (2017), 4325–4331.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats