Classification of a class of distance-regular graphs via completely regular codes

AbstractThe study of P-polynomial association schemes, or distance-regular graphs, and their possible classification is one of the main topics of algebraic combinatorics. One way to approach the issue is through the parameters pkij which characterize the scheme.The purpose of this paper is to deal with a concrete case. This case is also important in the study of the links between P-polynomial schemes and error-correcting codes.We present one way of constructing completely regular binary block-codes taking one kind of distance-regular graph as a starting point. The parameters of the code (length, error-correcting capability, minimum distance, covering radius, …) are calculable starting from the parameters pkij of the graph.We will use this construction to study an extremal case of distance-regular graphs leading to completely regular, uniformly packed codes, and we will use some well-known results concerning this type of code in order to find a solution to the problem of classifying the given graphs