Families of nested completely regular codes and distance-regular graphs

Joaquim  Borges; Josep Rifà; Victor A.  Zinoviev

doi:10.3934/amc.2015.9.233

Article Contents

2015, Volume 9, Issue 2: 233-246. Doi: 10.3934/amc.2015.9.233

This issue Previous Article Binary codes from reflexive uniform subset graphs on $3$-sets Next Article Cryptanalysis of a noncommutative key exchange protocol

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
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

Received: May 31, 2014

Published: April 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94B25; Secondary: 94B60.

Citation:

Related Papers

Cited by

References

[1]	L. A. Bassalygo, G. V. Zaitsev and V. A. Zinoviev, Uniformly packed codes, Problems Inform. Transmiss., 10 (1974), 9-14.
[2]	L. A. Bassalygo, V. A. Zinoviev, A note on uniformly packed codes, Problems Inform. Transmiss., 13 (1977), 22-25.
[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.
[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.
[5]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer, Berlin, 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-152.
[7]	P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Ph.D thesis, Katholieke Universiteit Leuven, Belgium, 1973.
[8]	A. Gardiner, Antipodal covering graphs, J. Combin. Theory Ser. B, 16 (1974), 255-273.
[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.
[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.
[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.
[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.
[13]	A. Neumaier, Completely regular codes, Discrete Math., 106/107 (1992), 335-360.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, Springer-Verlag, 1991, 360-367.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-5925.doi: 10.1109/TIT.2010.2103410.
[16]	P. Solé, Completely regular codes and completely transitive codes, Discrete Math., 81 (1990), 193-201.doi: 10.1016/0012-365X(90)90152-8.