Rad HAZU, Matematičke znanosti, Vol. 22 (2018), 23-38.

CODES FROM ORBIT MATRICES OF STRONGLY REGULAR GRAPHS

Dean Crnković, Marija Maksimović and Sanja Rukavina

Department of Mathematics, University of Rijeka, 51 000 Rijeka, Croatia
e-mail: deanc@math.uniri.hr

Department of Mathematics, University of Rijeka, 51 000 Rijeka, Croatia
e-mail: mmaksimovic@math.uniri.hr

Department of Mathematics, University of Rijeka, 51 000 Rijeka, Croatia
e-mail: sanjar@math.uniri.hr

Abstract.   We show that under certain conditions submatrices of orbit matrices of strongly regular graphs span self-orthogonal codes. In order to demonstrate this method of construction, we construct self-orthogonal binary linear codes from orbit matrices of the triangular graphs T(2k) with at most 120 vertices. Further, we obtain strongly regular graphs and block designs from codewords of the constructed codes.

2010 Mathematics Subject Classification.   05E30, 20D45, 94B05.

Key words and phrases.   Strongly regular graph, self-orthogonal code, block design.

Full text (PDF) (free access)

DOI: https://doi.org/10.21857/mwo1vczo8y

References:

  1. E. F. Assmus Jr. and J. D. Key, Designs and their Codes, Cambridge University Press, Cambridge, 1992, Cambridge Tracts in Mathematics, vol. 103 (second printing with corrections, 1993).
    MathSciNet     CrossRef

  2. M. Behbahani and C. Lam, Strongly regular graphs with non-trivial automorphisms, Discrete Math. 311 (2011), 132–144.
    MathSciNet     CrossRef

  3. T. Beth, D. Jungnickel and H. Lenz, Design Theory, Vol. I, Cambridge University Press, Cambridge, 1999.
    MathSciNet     CrossRef

  4. W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997) 235–265.
    MathSciNet     CrossRef

  5. A. E. Brouwer and C. J. van Eijl, On the p-rank of the adjacency matrices of strongly regular graphs, J. Algebraic Combin. 1 (1992), 329–346.
    MathSciNet     CrossRef

  6. A. E. Brouwer and J. H. van Lint, Strongly regular graphs and partial geometries, in: Enumeration and Design (eds. D. M. Jackson and S. A. Vanstone), Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982, Academic Press, Toronto, 1984, pp. 85–122.
    MathSciNet

  7. D. Crnković and S. Rukavina, Construction of block designs admitting an abelian automorphism group, Metrika 62 (2005), 175–183.
    MathSciNet     CrossRef

  8. D. Crnković, M. Maksimović, B. G. Rodrigues and S. Rukavina, Self-orthogonal codes from the strongly regular graphs on up to 40 vertices, Adv. Math. Commun. 10 (2016), 555–582.
    MathSciNet     CrossRef

  9. W. Fish, K. Kumwenda and E. Mwambene, Codes and designs from triangular graphs and their line graphs, Cent. Eur. J. Math. 9 (2011), 1411–1423.
    MathSciNet     CrossRef

  10. The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.8.10; 2018. (https://www.gap-system.org)

  11. W. H. Haemers, R. Peeters and J. M. van Rijckevorsel, Binary codes of strongly regular graphs, Des. Codes Cryptogr. 17 (1999), 187–209.
    MathSciNet     CrossRef

  12. M. Harada and V. D. Tonchev, Self-orthogonal codes from symmetric designs with fixed-point-free automorphisms, Discrete Math. 264 (2003), 81–90.
    MathSciNet     CrossRef

  13. Z. Janko, Coset enumeration in groups and constructions of symmetric designs, Combinatorics ’90 (Gaeta, 1990), 275–277, Ann. Discrete Math. 52, North-Holland, Amsterdam, 1992.
    MathSciNet     CrossRef

  14. J. D. Key, J. Moori and B. G. Rodrigues, Permutation decoding for the binary codes from triangular graphs, European J. Combin. 25 (2004), 113–123.
    MathSciNet     CrossRef

  15. L. H. Soicher, The GRAPE package for GAP, Version 4.6.1, 2012, http://www.maths.qmul.ac.uk/~leonard/grape/

  16. V. D. Tonchev, Combinatorial Configurations: Designs, Codes, Graphs, Pitman Monographs and Surveys in Pure and Applied Mathematics 40, Wiley, New York, 1988.
    MathSciNet

Rad HAZU Home Page