Volume 17, No 2, 2010, P. 3-19

UDC 621.391.15
S. V. Avgustinovich and I. Yu. Mogilnykh
Perfect 2-colorings of Johnson graphs J(8, 3) and J(8, 4)

Abstract:
In this paper we list all the matrices of parameters of perfect 2-colorings of Johnson graphs J(8,3) and J(8,4), give some constructions of perfect 2-colorings of Johnson graphs J(2w,w) and J(2m,3). The notion of perfect coloring is a generalization of the notion of completely regular code, introduced by Delsarte. The problem of existence of such structures in Johnson scheme is closely related to the problem of existence of completely regular codes in Johnson graphs, particularly to the Delsarte conjecture on nonexistence of nontrivial constant weight perfect codes, problem of existence of designs and other well-known mathematical problems.
Bibl. 19.

Keywords: perfect coloring, Johnson scheme, design.

Avgustinovich Sergey Vladimirovich ¹
Mogilnykh Ivan Yurevich ²
1. Nizhny Novgorod State University,
23 Gagarin ave., 603950 Nizhny Novgorod
e-mail: avgust@math.nsc.ru, ivmog84@gmail.com