RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2010 Volume 17, Issue 2, Pages 3–19 (Mi da602)

This article is cited in 26 papers

Perfect 2-colorings of Johnson graphs $J(8,3)$ and $J(8,4)$

S. V. Avgustinovichab, I. Yu. Mogilnykhab

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

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.

UDC: 621.391.15

Received: 10.08.2009


 English version:
Journal of Applied and Industrial Mathematics, 2011, 5:1, 19–30

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025