# American Institute of Mathematical Sciences

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-14.  Google Scholar [2] L. A. Bassalygo, V. A. Zinoviev, A note on uniformly packed codes, Problems Inform. Transmiss., 13 (1977), 22-25.  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-71. 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-148. doi: 10.1007/s10623-012-9713-3.  Google Scholar [5] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer, Berlin, 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-152.  Google Scholar [7] P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Ph.D thesis, Katholieke Universiteit Leuven, Belgium, 1973.  Google Scholar [8] A. Gardiner, Antipodal covering graphs, J. Combin. Theory Ser. B, 16 (1974), 255-273.  Google Scholar [9] M. Giudici and C. E. Praeger, Completely transitive codes in Hamming graphs, Europ. J. Combin., 20 (1999), 647-662. 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-238. 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-13. 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-394.  Google Scholar [13] A. Neumaier, Completely regular codes, Discrete Math., 106/107 (1992), 335-360. 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, Springer-Verlag, 1991, 360-367. 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-5925. doi: 10.1109/TIT.2010.2103410.  Google Scholar [16] P. Solé, Completely regular codes and completely transitive codes, Discrete Math., 81 (1990), 193-201. 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-14.  Google Scholar [2] L. A. Bassalygo, V. A. Zinoviev, A note on uniformly packed codes, Problems Inform. Transmiss., 13 (1977), 22-25.  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-71. 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-148. doi: 10.1007/s10623-012-9713-3.  Google Scholar [5] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer, Berlin, 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-152.  Google Scholar [7] P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Ph.D thesis, Katholieke Universiteit Leuven, Belgium, 1973.  Google Scholar [8] A. Gardiner, Antipodal covering graphs, J. Combin. Theory Ser. B, 16 (1974), 255-273.  Google Scholar [9] M. Giudici and C. E. Praeger, Completely transitive codes in Hamming graphs, Europ. J. Combin., 20 (1999), 647-662. 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-238. 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-13. 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-394.  Google Scholar [13] A. Neumaier, Completely regular codes, Discrete Math., 106/107 (1992), 335-360. 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, Springer-Verlag, 1991, 360-367. 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-5925. doi: 10.1109/TIT.2010.2103410.  Google Scholar [16] P. Solé, Completely regular codes and completely transitive codes, Discrete Math., 81 (1990), 193-201. 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] Dean Crnković, Ronan Egan, Andrea Švob. Self-orthogonal codes from orbit matrices of Seidel and Laplacian matrices of strongly regular graphs. Advances in Mathematics of Communications, 2020, 14 (4) : 591-602. doi: 10.3934/amc.2020032 [5] 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 [6] Sam Northshield. Quasi-regular graphs, cogrowth, and amenability. Conference Publications, 2003, 2003 (Special) : 678-687. doi: 10.3934/proc.2003.2003.678 [7] 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 [8] 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 [9] 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 [10] San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038 [11] Jinmei Fan, Yanhai Zhang. Optimal quinary negacyclic codes with minimum distance four. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021043 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] Bin Yu. Regular level sets of Lyapunov graphs of nonsingular Smale flows on 3-manifolds. Discrete & Continuous Dynamical Systems, 2011, 29 (3) : 1277-1290. doi: 10.3934/dcds.2011.29.1277 [20] 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

2020 Impact Factor: 0.935