Covering radius for codes obtained from T(m) triangular graphs

Triangular graphs are a special case of the well-known strongly regular graphs.

Taking any spanning tree in a T(m) triangular graph -m≥4- we get a fundamental circuit matrix for it. Using this matrix as a generator matrix we can obtain a single-error-correcting linear code C(T(m)) with parameters:

n=(m(m−1) (m−2))/2, k=(m(m−1) (m−3)+2)/2 and d=3.

Using the fact that each codeword in C(T(m)) is formed by a combination of simple circuits in T(m), we give a characterization of its codewords which allow us to show that:

1. (i)

   whatever the value of m be, if we take a hamiltonian path as a spanning tree in T(m), the obtained code C(T(m)) has covering radius σ equal to [m(m−1)/4] and

2. (ii)

   fixed m all the C(T(m)) codes are equivalent independently of the chosen spanning tree,

so, it is finally proved that given T(m) and any spanning tree in it, C(T(m)) has σ=[m(m−1)/4].

Authors and Affiliations

1. Departament d'Informàtica, Facultat de Ciències, Universitat Autònoma de Barcelona, 08193, Bellaterra Catalonia

   J. M. Basart & J. Rifà

Reprints and permissions

© 1989 Springer-Verlag Berlin Heidelberg

Policies and ethics