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]

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

[2]

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

[3]

Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045

[4]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, 2021, 20 (2) : 885-902. doi: 10.3934/cpaa.2020295

[5]

Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on Gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021014

[6]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[7]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017

[8]

Chunming Tang, Maozhi Xu, Yanfeng Qi, Mingshuo Zhou. A new class of $ p $-ary regular bent functions. Advances in Mathematics of Communications, 2021, 15 (1) : 55-64. doi: 10.3934/amc.2020042

[9]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124

[10]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[11]

Kateřina Škardová, Tomáš Oberhuber, Jaroslav Tintěra, Radomír Chabiniok. Signed-distance function based non-rigid registration of image series with varying image intensity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1145-1160. doi: 10.3934/dcdss.2020386

[12]

Mario Bukal. Well-posedness and convergence of a numerical scheme for the corrected Derrida-Lebowitz-Speer-Spohn equation using the Hellinger distance. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021001

[13]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[14]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129

[15]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044

[16]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[17]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053

[18]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065

[19]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055

[20]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]