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

Previous Article
On the existence of Hadamard difference sets in groups of order 400
AMC Home
This Issue
Next Article
There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$

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

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

Dean Crnković ^1, , Marija Maksimović ^1, , Bernardo Gabriel Rodrigues ^2, and Sanja Rukavina ^1,

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

Abstract
Related Papers

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.

Keywords: Strongly regular graph, orbit matrix., block design, code.

Mathematics Subject Classification: Primary: 05E30, 94B05; Secondary: 05B05, 20D4.

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.
[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.
[3]	T. Beth, D. Jungnickel and H. Lenz, Design Theory I,, Cambridge Univ. Press, (1999).
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	D. Crnković and S. Rukavina, On some symmetric $(45, 12, 3)$ and $(40,13, 4)$ designs,, J. Comput. Math. Optim., 1 (2005), 55.
[12]	M. Grassl, Bounds on the minimum distance of linear codes and quantum codes,, , (2016).
[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.
[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.
[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.
[16]	R. Hill and D. E. Newton, Optimal ternary linear codes,, Des. Codes Cryptogr., 2 (1992), 137. doi: 10.1007/BF00124893.
[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.
[18]	C. Jansen, K. Lux, R. Parker and R. Wilson, An Atlas of Brauer Characters,, Oxford Scient. Publ., (1995).
[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.
[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.
[21]	B. D. McKay and E. Spence, Classification of regular two-graphs on 36 and 38 vertices,, Austral. J. Combin., 24 (2001), 293.
[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.
[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.
[24]	L. D. Rudolph, A class of majority logic decodable codes,, IEEE Trans. Inform. Theory, 13 (1967), 305.
[25]	S. S. Sane and M. S. Shrikhande, Quasi-Symmetric Designs,, Cambridge Univ. Press, (1991). doi: 10.1017/CBO9780511665615.
[26]	E. Spence, The strongly regular $(40,12,2,4)$ graphs,, Electron. J. Combin., 7 (2000).
[27]	E. Spence, Strongly regular graphs on at most 64 vertices,, , (2016).
[28]	V. D. Tonchev, Codes,, in Handbook of Combinatorial Designs, (2007), 667.

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.
[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.
[3]	T. Beth, D. Jungnickel and H. Lenz, Design Theory I,, Cambridge Univ. Press, (1999).
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	D. Crnković and S. Rukavina, On some symmetric $(45, 12, 3)$ and $(40,13, 4)$ designs,, J. Comput. Math. Optim., 1 (2005), 55.
[12]	M. Grassl, Bounds on the minimum distance of linear codes and quantum codes,, , (2016).
[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.
[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.
[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.
[16]	R. Hill and D. E. Newton, Optimal ternary linear codes,, Des. Codes Cryptogr., 2 (1992), 137. doi: 10.1007/BF00124893.
[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.
[18]	C. Jansen, K. Lux, R. Parker and R. Wilson, An Atlas of Brauer Characters,, Oxford Scient. Publ., (1995).
[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.
[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.
[21]	B. D. McKay and E. Spence, Classification of regular two-graphs on 36 and 38 vertices,, Austral. J. Combin., 24 (2001), 293.
[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.
[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.
[24]	L. D. Rudolph, A class of majority logic decodable codes,, IEEE Trans. Inform. Theory, 13 (1967), 305.
[25]	S. S. Sane and M. S. Shrikhande, Quasi-Symmetric Designs,, Cambridge Univ. Press, (1991). doi: 10.1017/CBO9780511665615.
[26]	E. Spence, The strongly regular $(40,12,2,4)$ graphs,, Electron. J. Combin., 7 (2000).
[27]	E. Spence, Strongly regular graphs on at most 64 vertices,, , (2016).
[28]	V. D. Tonchev, Codes,, in Handbook of Combinatorial Designs, (2007), 667.

[1]	Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041
[2]	Cristian Dobre. Mathematical properties of the regular -representation of matrix $$-algebras with applications to semidefinite programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[3]	Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
[4]	Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[5]	Dequan Yue, Wuyi Yue. Block-partitioning matrix solution of M/M/R/N queueing system with balking, reneging and server breakdowns. Journal of Industrial & Management Optimization, 2009, 5 (3) : 417-430. doi: 10.3934/jimo.2009.5.417
[6]	Dung Le. On the regular set of BMO weak solutions to $p$-Laplacian strongly coupled nonregular elliptic systems. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : 3245-3265. doi: 10.3934/dcdsb.2014.19.3245
[7]	Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305
[8]	Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[9]	Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[10]	Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[11]	Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.
[12]	Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[13]	J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413
[14]	John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.
[15]	Matthias Rumberger. Lyapunov exponents on the orbit space. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 91-113. doi: 10.3934/dcds.2001.7.91
[16]	Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477
[17]	Shiqiu Liu, Frédérique Oggier. On applications of orbit codes to storage. Advances in Mathematics of Communications, 2016, 10 (1) : 113-130. doi: 10.3934/amc.2016.10.113
[18]	Tian Ma, Shouhong Wang. Block structure and block stability of two-dimensional incompressible flows. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 169-184. doi: 10.3934/dcdsb.2006.6.169
[19]	Kazumine Moriyasu, Kazuhiro Sakai, Kenichiro Yamamoto. Regular maps with the specification property. Discrete & Continuous Dynamical Systems - A, 2013, 33 (7) : 2991-3009. doi: 10.3934/dcds.2013.33.2991
[20]	Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261

2017 Impact Factor: 0.564

American Institute of Mathematical Sciences