August  2016, 10(3): 555-582. doi: 10.3934/amc.2016026

Self-orthogonal codes from the strongly regular graphs on up to 40 vertices

1. 

Department of Mathematics, University of Rijeka, Radmile Matejčić 2, 51000 Rijeka, Croatia

2. 

School of Mathematics, Statistics & Computer Science, University of KwaZulu-Natal, Durban 4000, South Africa

Received  May 2015 Revised  June 2016 Published  August 2016

This paper outlines a method for constructing self-orthogonal codes from orbit matrices of strongly regular graphs admitting an automorphism group $G$ which acts with orbits of length $w$, where $w$ divides $|G|$. We apply this method to construct self-orthogonal codes from orbit matrices of the strongly regular graphs with at most 40 vertices. In particular, we construct codes from adjacency or orbit matrices of graphs with parameters $(36, 15, 6, 6)$, $(36, 14, 4, 6)$, $(35, 16, 6, 8)$ and their complements, and from the graphs with parameters $(40, 12, 2, 4)$ and their complements. That completes the classification of self-orthogonal codes spanned by the adjacency matrices or orbit matrices of the strongly regular graphs with at most 40 vertices. Furthermore, we construct ternary codes of $2$-$(27,9,4)$ designs obtained as residual designs of the symmetric $(40, 13, 4)$ designs (complementary designs of the symmetric $(40, 27, 18)$ designs), and their ternary hulls. Some of the obtained codes are optimal, and some are best known for the given length and dimension.
Citation: Dean Crnković, Marija Maksimović, Bernardo Gabriel Rodrigues, Sanja Rukavina. Self-orthogonal codes from the strongly regular graphs on up to 40 vertices. Advances in Mathematics of Communications, 2016, 10 (3) : 555-582. doi: 10.3934/amc.2016026
References:
[1]

E. F. Assmus, Jr. and J. D. Key, Designs and their Codes,, Cambridge Univ. Press, (1992).  doi: 10.1017/CBO9781316529836.  Google Scholar

[2]

M. Behbahani and C. Lam, Strongly regular graphs with non-trivial automorphisms,, Discrete Math., 311 (2011), 132.  doi: 10.1016/j.disc.2010.10.005.  Google Scholar

[3]

T. Beth, D. Jungnickel and H. Lenz, Design Theory I,, Cambridge Univ. Press, (1999).   Google Scholar

[4]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language,, J. Symb. Comput., 24 (1997), 235.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[5]

I. Bouyukliev, On the binary projective codes with dimension 6,, Discrete Appl. Math., 154 (2006), 1693.  doi: 10.1016/j.dam.2006.03.004.  Google Scholar

[6]

I. Bouyukliev, V. Fack, W. Willems and J. Winne, Projective two-weight codes with small parameters and their corresponding graphs,, Des. Codes Cryptogr., 41 (2006), 59.  doi: 10.1007/s10623-006-0019-1.  Google Scholar

[7]

A. E. Brouwer and W. H. Haemers, Structure and uniqueness of the $(81,20,1,6)$ strongly regular graph,, Discrete Math., 106/107 (1992), 77.  doi: 10.1016/0012-365X(92)90532-K.  Google Scholar

[8]

D. Crnković, V. Mikulić Crnković and B. G. Rodrigues, Some optimal codes and strongly regular graphs from the linear group $L_4(3)$,, Util. Math., 89 (2012), 237.   Google Scholar

[9]

D. Crnković, B. G. Rodrigues, S. Rukavina and L. Simčić, Self-orthogonal codes from orbit matrices of $2$-designs,, Adv. Math. Commun., 7 (2013), 161.  doi: 10.3934/amc.2013.7.161.  Google Scholar

[10]

D. Crnković and S. Rukavina, Construction of block designs admitting an abelian automorphism group,, Metrika, 62 (2005), 175.  doi: 10.1007/s00184-005-0407-y.  Google Scholar

[11]

D. Crnković and S. Rukavina, On some symmetric $(45, 12, 3)$ and $(40,13, 4)$ designs,, J. Comput. Math. Optim., 1 (2005), 55.   Google Scholar

[12]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes,, , (2016).   Google Scholar

[13]

W. H. Haemers, R. Peeters and J. M. van Rijckevorsel, Binary codes of strongly regular graphs,, Des. Codes Cryptogr., 17 (1999), 187.  doi: 10.1023/A:1008353723204.  Google Scholar

[14]

N. Hamada, On the $p$-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its application to error correcting codes,, Hiroshima Math. J., 3 (1973), 153.   Google Scholar

[15]

M. Harada and V. D. Tonchev, Self-orthogonal codes from symmetric designswith fixed-point-free automorphisms,, Discrete Math., 264 (2003), 81.  doi: 10.1016/S0012-365X(02)00553-8.  Google Scholar

[16]

R. Hill and D. E. Newton, Optimal ternary linear codes,, Des. Codes Cryptogr., 2 (1992), 137.  doi: 10.1007/BF00124893.  Google Scholar

[17]

Z. Janko, Coset enumeration in groups and constructions of symmetric designs,, Ann. Discrete Math., 52 (1992), 275.  doi: 10.1016/S0167-5060(08)70919-1.  Google Scholar

[18]

C. Jansen, K. Lux, R. Parker and R. Wilson, An Atlas of Brauer Characters,, Oxford Scient. Publ., (1995).   Google Scholar

[19]

J. D. Key and K. Mackenzie-Fleming, Rigidity theorems for a class of affine resolvable designs,, J. Combin. Math. Combin. Comput., 35 (2000), 147.   Google Scholar

[20]

R. Mathon and A. Rosa, 2-$(v,k,\lambda)$ designs of small order,, in Handbook of Combinatorial Designs (eds. C.J. Colbourn and J.H. Dinitz), (2007), 25.   Google Scholar

[21]

B. D. McKay and E. Spence, Classification of regular two-graphs on 36 and 38 vertices,, Austral. J. Combin., 24 (2001), 293.   Google Scholar

[22]

B. G. Rodrigues, Self-orthogonal designs and codes from the symplectic groups $S_4(3)$ and $S_4(4)$,, Discrete Math., 308 (2008), 1941.  doi: 10.1016/j.disc.2007.04.047.  Google Scholar

[23]

B. G. Rodrigues, Some optimal codes related to graphs invariant under the alternating group $A_8$,, Adv. Math. Commun., 5 (2011), 339.  doi: 10.3934/amc.2011.5.339.  Google Scholar

[24]

L. D. Rudolph, A class of majority logic decodable codes,, IEEE Trans. Inform. Theory, 13 (1967), 305.   Google Scholar

[25]

S. S. Sane and M. S. Shrikhande, Quasi-Symmetric Designs,, Cambridge Univ. Press, (1991).  doi: 10.1017/CBO9780511665615.  Google Scholar

[26]

E. Spence, The strongly regular $(40,12,2,4)$ graphs,, Electron. J. Combin., 7 (2000).   Google Scholar

[27]

E. Spence, Strongly regular graphs on at most 64 vertices,, , (2016).   Google Scholar

[28]

V. D. Tonchev, Codes,, in Handbook of Combinatorial Designs, (2007), 667.   Google Scholar

show all references

References:
[1]

E. F. Assmus, Jr. and J. D. Key, Designs and their Codes,, Cambridge Univ. Press, (1992).  doi: 10.1017/CBO9781316529836.  Google Scholar

[2]

M. Behbahani and C. Lam, Strongly regular graphs with non-trivial automorphisms,, Discrete Math., 311 (2011), 132.  doi: 10.1016/j.disc.2010.10.005.  Google Scholar

[3]

T. Beth, D. Jungnickel and H. Lenz, Design Theory I,, Cambridge Univ. Press, (1999).   Google Scholar

[4]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language,, J. Symb. Comput., 24 (1997), 235.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[5]

I. Bouyukliev, On the binary projective codes with dimension 6,, Discrete Appl. Math., 154 (2006), 1693.  doi: 10.1016/j.dam.2006.03.004.  Google Scholar

[6]

I. Bouyukliev, V. Fack, W. Willems and J. Winne, Projective two-weight codes with small parameters and their corresponding graphs,, Des. Codes Cryptogr., 41 (2006), 59.  doi: 10.1007/s10623-006-0019-1.  Google Scholar

[7]

A. E. Brouwer and W. H. Haemers, Structure and uniqueness of the $(81,20,1,6)$ strongly regular graph,, Discrete Math., 106/107 (1992), 77.  doi: 10.1016/0012-365X(92)90532-K.  Google Scholar

[8]

D. Crnković, V. Mikulić Crnković and B. G. Rodrigues, Some optimal codes and strongly regular graphs from the linear group $L_4(3)$,, Util. Math., 89 (2012), 237.   Google Scholar

[9]

D. Crnković, B. G. Rodrigues, S. Rukavina and L. Simčić, Self-orthogonal codes from orbit matrices of $2$-designs,, Adv. Math. Commun., 7 (2013), 161.  doi: 10.3934/amc.2013.7.161.  Google Scholar

[10]

D. Crnković and S. Rukavina, Construction of block designs admitting an abelian automorphism group,, Metrika, 62 (2005), 175.  doi: 10.1007/s00184-005-0407-y.  Google Scholar

[11]

D. Crnković and S. Rukavina, On some symmetric $(45, 12, 3)$ and $(40,13, 4)$ designs,, J. Comput. Math. Optim., 1 (2005), 55.   Google Scholar

[12]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes,, , (2016).   Google Scholar

[13]

W. H. Haemers, R. Peeters and J. M. van Rijckevorsel, Binary codes of strongly regular graphs,, Des. Codes Cryptogr., 17 (1999), 187.  doi: 10.1023/A:1008353723204.  Google Scholar

[14]

N. Hamada, On the $p$-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its application to error correcting codes,, Hiroshima Math. J., 3 (1973), 153.   Google Scholar

[15]

M. Harada and V. D. Tonchev, Self-orthogonal codes from symmetric designswith fixed-point-free automorphisms,, Discrete Math., 264 (2003), 81.  doi: 10.1016/S0012-365X(02)00553-8.  Google Scholar

[16]

R. Hill and D. E. Newton, Optimal ternary linear codes,, Des. Codes Cryptogr., 2 (1992), 137.  doi: 10.1007/BF00124893.  Google Scholar

[17]

Z. Janko, Coset enumeration in groups and constructions of symmetric designs,, Ann. Discrete Math., 52 (1992), 275.  doi: 10.1016/S0167-5060(08)70919-1.  Google Scholar

[18]

C. Jansen, K. Lux, R. Parker and R. Wilson, An Atlas of Brauer Characters,, Oxford Scient. Publ., (1995).   Google Scholar

[19]

J. D. Key and K. Mackenzie-Fleming, Rigidity theorems for a class of affine resolvable designs,, J. Combin. Math. Combin. Comput., 35 (2000), 147.   Google Scholar

[20]

R. Mathon and A. Rosa, 2-$(v,k,\lambda)$ designs of small order,, in Handbook of Combinatorial Designs (eds. C.J. Colbourn and J.H. Dinitz), (2007), 25.   Google Scholar

[21]

B. D. McKay and E. Spence, Classification of regular two-graphs on 36 and 38 vertices,, Austral. J. Combin., 24 (2001), 293.   Google Scholar

[22]

B. G. Rodrigues, Self-orthogonal designs and codes from the symplectic groups $S_4(3)$ and $S_4(4)$,, Discrete Math., 308 (2008), 1941.  doi: 10.1016/j.disc.2007.04.047.  Google Scholar

[23]

B. G. Rodrigues, Some optimal codes related to graphs invariant under the alternating group $A_8$,, Adv. Math. Commun., 5 (2011), 339.  doi: 10.3934/amc.2011.5.339.  Google Scholar

[24]

L. D. Rudolph, A class of majority logic decodable codes,, IEEE Trans. Inform. Theory, 13 (1967), 305.   Google Scholar

[25]

S. S. Sane and M. S. Shrikhande, Quasi-Symmetric Designs,, Cambridge Univ. Press, (1991).  doi: 10.1017/CBO9780511665615.  Google Scholar

[26]

E. Spence, The strongly regular $(40,12,2,4)$ graphs,, Electron. J. Combin., 7 (2000).   Google Scholar

[27]

E. Spence, Strongly regular graphs on at most 64 vertices,, , (2016).   Google Scholar

[28]

V. D. Tonchev, Codes,, in Handbook of Combinatorial Designs, (2007), 667.   Google Scholar

[1]

Evan Greif, Daniel Kaplan, Robert S. Strichartz, Samuel C. Wiese. Spectrum of the Laplacian on regular polyhedra. Communications on Pure & Applied Analysis, 2021, 20 (1) : 193-214. doi: 10.3934/cpaa.2020263

[2]

Thomas Bartsch, Tian Xu. Strongly localized semiclassical states for nonlinear Dirac equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 29-60. doi: 10.3934/dcds.2020297

[3]

Guangbin CAI, Yang Zhao, Wanzhen Quan, Xiusheng Zhang. Design of LPV fault-tolerant controller for hypersonic vehicle based on state observer. Journal of Industrial & Management Optimization, 2021, 17 (1) : 447-465. doi: 10.3934/jimo.2019120

[4]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[5]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[6]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

[7]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[8]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435

[9]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[10]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[11]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[12]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (143)
  • HTML views (0)
  • Cited by (2)

[Back to Top]