Extremal 1-codes in distance-regular graphs of diameter 3

Designs, Codes and Cryptography - Tập 65 - Trang 29-47 - 2012
Aleksandar Jurišić1,2, Janoš Vidali2
1Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
2Faculty of Computer and Information Science, University of Ljubljana, Ljubljana, Slovenia

Tóm tắt

We study 1-codes in distance-regular graphs of diameter 3 that achieve three different bounds. We show that the intersection array of a distance-regular graph containing such a code has the form $${\{a(p+1), cp, a+1; 1, c, a p\}\quad{\rm or}\quad\{a(p+1), (a+1)p,c; 1, c, a p\}}$$ for c =  c 2, a =  a 3 and $${p = p_{33}^3}$$ . These two families contain 10 + 15 known feasible intersection arrays out of which four are uniquely realized by the Sylvester graph, the Hamming graph H(3, 3), the Doro graph and the Johnson graph J(9, 3), but not all members of these two families are feasible. We construct four new one-parameter infinite subfamilies of feasible intersection arrays, two of which have a nontrivial vanishing Krein parameter: $${\{(2r^2-1)(2r+1), 4r(r^2-1), 2r^2; 1, 2(r^2-1), r(4r^2-2)\}}$$ and $${\{2r^2(2r+1), (2r-1)(2r^2+r+1), 2r^2; 1, 2r^2, r(4r^2-1)\}}$$ for r > 1 (the second family actually generalizes to a two-parameter family with the same property). Using this information we calculate some triple intersection numbers for these two families to show that they must contain the desired code. Finally, we use some additional combinatorial arguments to prove nonexistence of distance-regular graphs with such intersection arrays.

Tài liệu tham khảo

Brouwer A.E., Cohen A.M., Neumaier A.: Distance-Regular Graphs. Springer, Berlin (1989) Coolsaet K., Jurišić A.: Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs. J. Comb. Theory Ser. A 115(6), 1086–1095 (2008) Godsil C.D.: Algebraic Combinatorics. Chapman and Hall Mathematics Series. Chapman & Hall, New York (1993) Koolen J., Park J.: Shilla distance-regular graphs. Eur. J. Comb. 31(8), 2064–2073 (2010) Terwilliger P.: A characterization of P- and Q-polynomial association schemes. J. Comb. Theory Ser. A 45(1), 8–26 (1987)