2015, 9(2): 233-246. doi: 10.3934/amc.2015.9.233

Families of nested completely regular codes and distance-regular graphs

1. 

Department of Information and Communications Engineering, Universitat Autònoma de Barcelona, 08193 Bellaterra, Cerdanyola del Vallès, Spain

2. 

Department of Information and Communications Engineering, Universitat Autònoma de Barcelona, 08193-Bellaterra, Cerdanyola del Vallès

3. 

A. A. Kharkevich Institute for Problems of Information Transmission, Russian Academy of Sciences, GSP-4, Moscow, 127994, Russian Federation

Received  June 2014 Published  May 2015

In this paper infinite families of linear binary nested completely regular codes are constructed. They have covering radius $\rho$ equal to $3$ or $4,$ and are $1/2^i$th parts, for $i\in\{1,\ldots,u\}$ of binary (respectively, extended binary) Hamming codes of length $n=2^m-1$ (respectively, $2^m$), where $m=2u$. In the usual way, i.e., as coset graphs, infinite families of embedded distance-regular coset graphs of diameter $D$ equal to $3$ or $4$ are constructed. This gives antipodal covers of some distance-regular and distance-transitive graphs. In some cases, the constructed codes are also completely transitive and the corresponding coset graphs are distance-transitive.
Citation: Joaquim Borges, Josep Rifà, Victor A. Zinoviev. Families of nested completely regular codes and distance-regular graphs. Advances in Mathematics of Communications, 2015, 9 (2) : 233-246. doi: 10.3934/amc.2015.9.233
References:
[1]

L. A. Bassalygo, G. V. Zaitsev and V. A. Zinoviev, Uniformly packed codes,, Problems Inform. Transmiss., 10 (1974), 9.

[2]

L. A. Bassalygo, V. A. Zinoviev, A note on uniformly packed codes,, Problems Inform. Transmiss., 13 (1977), 22.

[3]

J. Borges, J. Rifà and V. A. Zinoviev, Families of completely transitive codes and distance transitive graphs,, Discrete Math., 324 (2014), 68. doi: 10.1016/j.disc.2014.02.008.

[4]

J. Borges, J. Rifà and V. A. Zinoviev, New families of completely regular codes and their corresponding distance regular coset graphs,, Des. Codes Crypt., 70 (2014), 139. doi: 10.1007/s10623-012-9713-3.

[5]

A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs,, Springer, (1989). doi: 10.1007/978-3-642-74341-2.

[6]

A. M. Calderbank and J. M. Goethals, Three-weights codes and association schemes,, Philips J. Res., 39 (1984), 143.

[7]

P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory,, Ph.D thesis, (1973).

[8]

A. Gardiner, Antipodal covering graphs,, J. Combin. Theory Ser. B, 16 (1974), 255.

[9]

M. Giudici and C. E. Praeger, Completely transitive codes in Hamming graphs,, Europ. J. Combin., 20 (1999), 647. doi: 10.1006/eujc.1999.0313.

[10]

C. D. Godsil and A. D. Hensel, Distance regular covers of the complete graph,, J. Combin. Theory Ser. B, 56 (1992), 205. doi: 10.1016/0095-8956(92)90019-T.

[11]

A. A. Ivanov, R. A. Lieber, T. Penttila and C. E. Praeger, Antipodal distance-transitive covers of complete bipartite graphs,, Europ. J. Combin., 18 (1997), 11. doi: 10.1006/eujc.1993.0086.

[12]

T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes,, Inform. Control, 18 (1971), 369.

[13]

A. Neumaier, Completely regular codes,, Discrete Math., 106/107 (1992), 335. doi: 10.1016/0012-365X(92)90565-W.

[14]

J. Rifà and J. Pujol, Completely transitive codes and distance transitive graphs,, in Proc. 9th Int. Conf. AAECC, (1991), 360. doi: 10.1007/3-540-54522-0_124.

[15]

J. Rifà and V. A. Zinoviev, On lifting perfect codes,, IEEE Trans. Inf. Theory, 57 (2011), 5918. doi: 10.1109/TIT.2010.2103410.

[16]

P. Solé, Completely regular codes and completely transitive codes,, Discrete Math., 81 (1990), 193. doi: 10.1016/0012-365X(90)90152-8.

show all references

References:
[1]

L. A. Bassalygo, G. V. Zaitsev and V. A. Zinoviev, Uniformly packed codes,, Problems Inform. Transmiss., 10 (1974), 9.

[2]

L. A. Bassalygo, V. A. Zinoviev, A note on uniformly packed codes,, Problems Inform. Transmiss., 13 (1977), 22.

[3]

J. Borges, J. Rifà and V. A. Zinoviev, Families of completely transitive codes and distance transitive graphs,, Discrete Math., 324 (2014), 68. doi: 10.1016/j.disc.2014.02.008.

[4]

J. Borges, J. Rifà and V. A. Zinoviev, New families of completely regular codes and their corresponding distance regular coset graphs,, Des. Codes Crypt., 70 (2014), 139. doi: 10.1007/s10623-012-9713-3.

[5]

A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs,, Springer, (1989). doi: 10.1007/978-3-642-74341-2.

[6]

A. M. Calderbank and J. M. Goethals, Three-weights codes and association schemes,, Philips J. Res., 39 (1984), 143.

[7]

P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory,, Ph.D thesis, (1973).

[8]

A. Gardiner, Antipodal covering graphs,, J. Combin. Theory Ser. B, 16 (1974), 255.

[9]

M. Giudici and C. E. Praeger, Completely transitive codes in Hamming graphs,, Europ. J. Combin., 20 (1999), 647. doi: 10.1006/eujc.1999.0313.

[10]

C. D. Godsil and A. D. Hensel, Distance regular covers of the complete graph,, J. Combin. Theory Ser. B, 56 (1992), 205. doi: 10.1016/0095-8956(92)90019-T.

[11]

A. A. Ivanov, R. A. Lieber, T. Penttila and C. E. Praeger, Antipodal distance-transitive covers of complete bipartite graphs,, Europ. J. Combin., 18 (1997), 11. doi: 10.1006/eujc.1993.0086.

[12]

T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes,, Inform. Control, 18 (1971), 369.

[13]

A. Neumaier, Completely regular codes,, Discrete Math., 106/107 (1992), 335. doi: 10.1016/0012-365X(92)90565-W.

[14]

J. Rifà and J. Pujol, Completely transitive codes and distance transitive graphs,, in Proc. 9th Int. Conf. AAECC, (1991), 360. doi: 10.1007/3-540-54522-0_124.

[15]

J. Rifà and V. A. Zinoviev, On lifting perfect codes,, IEEE Trans. Inf. Theory, 57 (2011), 5918. doi: 10.1109/TIT.2010.2103410.

[16]

P. Solé, Completely regular codes and completely transitive codes,, Discrete Math., 81 (1990), 193. doi: 10.1016/0012-365X(90)90152-8.

[1]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021

[2]

Joaquim Borges, Josep Rifà, Victor A. Zinoviev. On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual. Advances in Mathematics of Communications, 2010, 4 (4) : 567-578. doi: 10.3934/amc.2010.4.567

[3]

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

[4]

Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131

[5]

Sam Northshield. Quasi-regular graphs, cogrowth, and amenability. Conference Publications, 2003, 2003 (Special) : 678-687. doi: 10.3934/proc.2003.2003.678

[6]

Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015

[7]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019

[8]

Carlos Munuera, Morgan Barbier. Wet paper codes and the dual distance in steganography. Advances in Mathematics of Communications, 2012, 6 (3) : 273-285. doi: 10.3934/amc.2012.6.273

[9]

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

[10]

Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93

[11]

Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175

[12]

Andries E. Brouwer, Tuvi Etzion. Some new distance-4 constant weight codes. Advances in Mathematics of Communications, 2011, 5 (3) : 417-424. doi: 10.3934/amc.2011.5.417

[13]

Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005

[14]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65

[15]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018

[16]

Bin Yu. Regular level sets of Lyapunov graphs of nonsingular Smale flows on 3-manifolds. Discrete & Continuous Dynamical Systems - A, 2011, 29 (3) : 1277-1290. doi: 10.3934/dcds.2011.29.1277

[17]

Jennifer D. Key, Washiela Fish, Eric Mwambene. Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$. Advances in Mathematics of Communications, 2011, 5 (2) : 373-394. doi: 10.3934/amc.2011.5.373

[18]

Cristóbal Camarero, Carmen Martínez, Ramón Beivide. Identifying codes of degree 4 Cayley graphs over Abelian groups. Advances in Mathematics of Communications, 2015, 9 (2) : 129-148. doi: 10.3934/amc.2015.9.129

[19]

Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal. Zig-zag and replacement product graphs and LDPC codes. Advances in Mathematics of Communications, 2008, 2 (4) : 347-372. doi: 10.3934/amc.2008.2.347

[20]

Emmanuel Charbit, Irène Charon, Gérard Cohen, Olivier Hudry, Antoine Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Advances in Mathematics of Communications, 2008, 2 (4) : 403-420. doi: 10.3934/amc.2008.2.403

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]