Codes and designs from triangular graphs and their line graphs

• Autorzy: Washiela Fish , Khumbo Kumwenda , Eric Mwambene
• Języki publikacji: EN

Abstrakty

EN

For any prime p, we consider p-ary linear codes obtained from the span over $\mathbb{F}_p $ p of rows of incidence matrices of triangular graphs, differences of the rows and adjacency matrices of line graphs of triangular graphs. We determine parameters of the codes, minimum words and automorphism groups. We also show that the codes can be used for full permutation decoding.

Słowa kluczowe

EN

Automorphism group; Incidence design; Incidence matrix; Line graph; Linear code; Permutation decoding; Triangular graph

Kategorie tematyczne

• 94B35: Decoding
• 94B05: Linear codes, general

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2011
• Tom: 9
• Numer: 6
• Strony: 1411-1423

Daty

wydano

2011-12-01

online

2011-09-23

Twórcy

autor

Washiela Fish

• University of the Western Cape

autor

Khumbo Kumwenda

• University of the Western Cape

autor

Eric Mwambene

• University of the Western Cape

Bibliografia

• [1] Andrásfai B., Graph Theory: Flows, Matrices, Adam Hilger, Bristol, 1991
• [2] Assmus E.F. Jr., Key J.D., Designs and their Codes, Cambridge Tracts in Math., 103, Cambridge University Press, Cambridge, 1992
• [3] Bosma W., Cannon J., Playoust C., The Magma algebra system. I. The user language, J. Symbolic Comput., 1997, 24(3–4), 235–265 http://dx.doi.org/10.1006/jsco.1996.0125
• [4] Fish W., Key J.D., Mwambene E., Codes from incidence matrices and line graphs of Hamming graphs, Discrete Math., 2011, 310(13–14), 1884–1897
• [5] Fish W., Key J.D., Mwambene E., Codes from the incidence matrices of graphs on 3-sets, Discrete Math., 2011, 311(6), 1823–1840 http://dx.doi.org/10.1016/j.disc.2011.04.029
• [6] Frucht R., On the groups of repeated graphs, Bull. Amer. Math. Soc., 1949, 55(4), 418–420 http://dx.doi.org/10.1090/S0002-9904-1949-09230-3
• [7] Gordon D.M., Minimal permutation sets for decoding the binary Golay codes, IEEE Trans. Inform. Theory, 1982, 28(3), 541–543 http://dx.doi.org/10.1109/TIT.1982.1056504
• [8] Grassl M., Bounds on the minimum distance of linear codes and quantum codes, available at http://www.codetables.de
• [9] Haemers W.H., Peeters R., van Rijckevorsel J.M., Binary codes of strongly regular graphs, Des. Codes Cryptogr., 1999, 17, 187–209 http://dx.doi.org/10.1023/A:1026479210284
• [10] Huffman W.C., Codes and groups, In: Handbook of Coding Theory, Vol. II. North-Holland, Amsterdam, 1998, 1345–1440
• [11] Key J.D., Fish W., Mwambene E., Codes from incidence matrices and line graphs of Hamming graphs H k (n, 2) for k ≥ 2, Adv. Math. Commun., 2011, 5(2), 373–394 http://dx.doi.org/10.3934/amc.2011.5.373
• [12] Key J.D., McDonough T.P., Mavron V.C., Information sets and partial permutation decoding for codes from finite geometries, Finite Fields Appl., 2006, 12(2), 232–247 http://dx.doi.org/10.1016/j.ffa.2005.05.007
• [13] Key J.D., Moori J., Rodrigues B.G., Permutation decoding for the binary codes from triangular graphs, European J. Combin., 2004, 25(1), 113–123 http://dx.doi.org/10.1016/j.ejc.2003.08.001
• [14] Key J.D., Moori J., Rodrigues B.G., Codes associated with triangular graphs and permutation decoding, Int. J. Inf. Coding Theory, 2010, 1(3), 334–349 http://dx.doi.org/10.1504/IJICOT.2010.032547
• [15] Kumwenda K., Mwambene E., Codes from graphs related to categorical products of triangular graphs and K n, In: IEEE Information Theory Workshop, Dublin, 30 August–3 September 2010, DOI: 10.1109/CIG.2010.5592662
• [16] Little C.H.C., Grant D.D., Holton D.A., On defect-d matchings in graphs, Discrete Math., 1975, 13, 41–54 http://dx.doi.org/10.1016/0012-365X(75)90085-0
• [17] MacWilliams F.J., Permutation decoding of systematic codes, Bell System Tech. J., 1964, 43, 485–505
• [18] MacWilliams F.J., Sloane N.J.A., The Theory of Error-Correcting Codes, North-Holland Math. Library, 16, North-Holland, Amsterdam-New York-Oxford, 1977
• [19] Rodrigues B.G., Codes of Designs and Graphs from Finite Simple Groups, Ph.D. thesis, University of Natal, Pietermaritzburg, 2003
• [20] Tonchev V.D., Combinatorial Configurations: Designs, Codes, Graphs, Pitman Monogr. Surveys Pure Appl. Math., 40, Longman Scientific and Technical, Harlow, 1988
• [21] Whitney H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 1932, 54(1), 150–168 http://dx.doi.org/10.2307/2371086

Identyfikatory

DOI

10.2478/s11533-011-0072-5