May  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. Google Scholar

[2]

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

[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. Google Scholar

[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. Google Scholar

[5]

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

[6]

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

[7]

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

[8]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[12]

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

[13]

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

[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. Google Scholar

[15]

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

[16]

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

show all references

References:
[1]

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

[2]

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

[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. Google Scholar

[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. Google Scholar

[5]

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

[6]

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

[7]

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

[8]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[12]

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

[13]

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

[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. Google Scholar

[15]

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

[16]

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

[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

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]