Special LCD codes from products of graphs. (English) Zbl 1518.05117
Summary: We examine the binary codes from the adjacency matrices of various products of graphs, and show that if the binary codes of a set of graphs have the property that their dual codes are the codes of the associated reflexive graphs, and are thus LCD, i.e. have zero hull, then, with some restrictions, the binary code of the product will have the same property. The codes are candidates for decoding using this property, or also, in the case of the direct product, by permutation decoding.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 94B05 | Linear codes (general theory) |
Software:
MagmaReferences:
| [1] | Assmus, E.F., Jr, Key, J.D.: Designs and Their Codes. Cambridge University Press, Cambridge (1992) (Cambridge Tracts in Mathematics, vol. 103, Second printing with corrections, 1993) · Zbl 0762.05001 |
| [2] | Barik, S.; Bapat, RB; Pati, S., On the Laplacian spectra of product graphs, Appl. Anal. Disc. Math., 9, 39-58 (2015) · Zbl 1464.05226 · doi:10.2298/AADM150218006B |
| [3] | Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system I: the user language, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125 |
| [4] | Cannon, J., Steel, A., White, G.: Linear codes over finite fields. In: Cannon, J., Bosma, W. (eds.) Handbook of Magma Functions, V2.13, pp. 3951-4023. Computational Algebra Group, Department of Mathematics, University of Sydney (2006). http://magma.maths.usyd.edu.au/magma |
| [5] | Fiedler, M., Algebraic connectivity of graphs, Czechoslovak Math. J., 23, 298-305 (1973) · Zbl 0265.05119 · doi:10.21136/CMJ.1973.101168 |
| [6] | Fish, W.; Key, JD; Mwambene, E.; Rodrigues, BG, Hamming graphs and LCD codes, J. Appl. Math. Comput., 61, 461-479 (2019) · Zbl 1427.94090 · doi:10.1007/s12190-019-01259-w |
| [7] | Daniel, DM, Minimal permutation sets for decoding the binary Golay codes, IEEE Trans. Inform. Theory, 28, 541-543 (1982) · Zbl 0479.94021 · doi:10.1109/TIT.1982.1056504 |
| [8] | Haemers, W.H., Peeters, R., van Rijckevorsel, J.M.: Binary codes of strongly regular graphs. Des Codes Cryptogr. 17, 187-209 (1999) · Zbl 0938.05062 |
| [9] | Hammack, R., Imrich, W., Klavžar, S.: Handbook of Product Graphs, 2nd edn. CRC Press, Boca Raton (2011) · Zbl 1283.05001 |
| [10] | Huffman, W.C..: Codes and groups. In: Pless, V.S., Huffman, W.C. (eds.) Handbook of Coding Theory, vol 2, part 2, chapt 17, pp. 1345-1440. Elsevier, Amsterdam (1998) · Zbl 0926.94039 |
| [11] | Key, JD; Limbupasiriporn, J., Permutation decoding of codes from Paley graphs, Congr. Numer., 170, 143-155 (2004) · Zbl 1071.94028 |
| [12] | Key, JD; McDonough, TP; Mavron, VC, Partial permutation decoding for codes from finite planes, Eur. J. Combin., 26, 665-682 (2005) · Zbl 1074.94014 · doi:10.1016/j.ejc.2004.04.007 |
| [13] | Key, JD; McDonough, TP; Mavron, VC, Information sets and partial permutation decoding for codes from finite geometries, Finite Fields Appl., 12, 232-247 (2006) · Zbl 1089.94044 · doi:10.1016/j.ffa.2005.05.007 |
| [14] | Key, JD; McDonough, TP; Mavron, VC, Improved partial permutation decoding for Reed-Muller codes, Disc. Math., 340, 722-728 (2017) · Zbl 1393.94931 · doi:10.1016/j.disc.2016.11.031 |
| [15] | Key, JD; Moori, J.; Rodrigues, BG, Permutation decoding for binary codes from triangular graphs, Eur. J. Combin., 25, 113-123 (2004) · Zbl 1049.94024 · doi:10.1016/j.ejc.2003.08.001 |
| [16] | Key, JD; Rodrigues, BG, \({LCD}\) codes from adjacency matrices of graphs, Appl. Algebra Engrg. Comm. Comput., 29, 3, 227-244 (2018) · Zbl 1391.94846 · doi:10.1007/s00200-017-0339-6 |
| [17] | Key, JD; Rodrigues, BG, Special \({LCD}\) codes from Peisert and generalized Peisert graphs, Graphs Combin., 35, 633-652 (2019) · Zbl 1462.94066 · doi:10.1007/s00373-019-02019-0 |
| [18] | Key, JD; Rodrigues, BG, Binary codes from \(m\)-ary \(n\)-cubes \({Q}^m_n\), Adv. Math. Commun., 15, 3, 507-524 (2021) · Zbl 1465.94108 · doi:10.3934/amc.2020079 |
| [19] | Key, J.D., Rodrigues, B.G.: Minimal \({PD}\)-sets associated with the graphs \({Q}^m_2, m\) even. Appl. Algebra Eng. Commun. Comput. (2021) (to appear). https://doi.org/10.1007/s00200-020-00481-5 · Zbl 1527.94088 |
| [20] | Kroll, H.-J., Taherian, S.-G., Vincenti, R.: Optimal antiblocking information systems for the binary codes related to triangular graphs. Adv. Math. Commun. (2020) (to appear). doi:10.3934/amc.2020107 · Zbl 1483.94069 |
| [21] | Kroll, H.-J., Vincenti, R.: PD-sets related to the codes of some classical varieties. Discr. Math. 301, 89-105 (2005) · Zbl 1087.94024 |
| [22] | MacWilliams, FJ, Permutation decoding of systematic codes, Bell Syst. Tech. J., 43, 485-505 (1964) · Zbl 0116.35304 · doi:10.1002/j.1538-7305.1964.tb04075.x |
| [23] | MacWilliams, FJ; Sloane, NJA, The Theory of Error-Correcting Codes (1983), Amsterdam: North-Holland, Amsterdam · Zbl 0369.94008 |
| [24] | James, L., Massey, Linear codes with complementary duals, Disc. Math., 106, 107, 337-342 (1992) · Zbl 0754.94009 |
| [25] | Merris, R., Laplacian matrices of graphs? A survey, Linear Algeb. Appl., 197, 198, 143-176 (1994) · Zbl 0802.05053 · doi:10.1016/0024-3795(94)90486-3 |
| [26] | Schönheim, J., On coverings, Pacific J. Math., 14, 1405-1411 (1964) · Zbl 0128.24501 · doi:10.2140/pjm.1964.14.1405 |
| [27] | Shi, M., Huang, D., Sok, L., Solé, P.: Double circulant LCD codes over \(\mathbb{Z}_4\). Finite Fields Appl. 58, 133-144 (2019) · Zbl 1456.94138 |
| [28] | Tonchev, V.D.: Combinatorial Configurations, Designs, Codes, Graphs. Pitman Monographs and Surveys in Pure and Applied Mathematics, No. 40. Longman, New York (1988) (Translated from the Bulgarian by Robert A. Melter) · Zbl 0643.05002 |
| [29] | West, D.B.: Introduction to Graph Theory. Prentice Hall (1996) · Zbl 0845.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
