Geodesic
Perfect 2-colorings of Johnson graphs $J(8,3)$ and $J(8,4)$
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 2, pp. 3-19.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2010_17_2_a0,
     author = {S. V. Avgustinovich and I. Yu. Mogilnykh},
     title = {Perfect 2-colorings of {Johnson} graphs $J(8,3)$ and $J(8,4)$},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--19},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_2_a0/}
}
TY  - JOUR
AU  - S. V. Avgustinovich
AU  - I. Yu. Mogilnykh
TI  - Perfect 2-colorings of Johnson graphs $J(8,3)$ and $J(8,4)$
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 3
EP  - 19
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_2_a0/
LA  - ru
ID  - DA_2010_17_2_a0
ER  - 
%0 Journal Article
%A S. V. Avgustinovich
%A I. Yu. Mogilnykh
%T Perfect 2-colorings of Johnson graphs $J(8,3)$ and $J(8,4)$
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 3-19
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_2_a0/
%G ru
%F DA_2010_17_2_a0
S. V. Avgustinovich; I. Yu. Mogilnykh. Perfect 2-colorings of Johnson graphs $J(8,3)$ and $J(8,4)$. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 2, pp. 3-19. http://geodesic.mathdoc.fr/item/DA_2010_17_2_a0/

[1] Mogilnykh I. Yu., “O regulyarnosti sovershennykh raskrasok grafa Dzhonsona v dva tsveta”, Probl. peredachi inform., 43:4 (2007), 37–44 | MR

[2] Mogilnykh I. Yu., “O nesuschestvovanii nekotorykh sovershennykh 2-raskrasok grafov Dzhonsona”, Diskret. analiz i issled. operatsii, 16:5 (2009), 52–68 | MR

[3] Tsvetkovich D., Dub M., Zakhs Kh., Spektry grafov: teoriya i primenenie, Naukova Dumka, Kiev, 1984, 384 pp. | MR

[4] Fon-der-Flaasc D. G., “Sovershennye 2-raskraski 12-mernogo kuba, dostigayuschie granitsy korrelyatsionnoi immunnosti”, Sib. elektron. mat. izv., 2007, no. 4, 292–295 | MR

[5] Fon-der-Flaasc D. G., “Sovershennye 2-raskraski giperkuba”, Sib. mat. zhurn., 48:4 (2007), 923–930 | MR | Zbl

[6] Dehon M., “On the existence of 2-designs $S_\lambda(2,3,v)$ without repeated blocks”, Discrete Math., 43 (1961), 155–171 | DOI | MR

[7] Delsarte P., “An algebraic approach to the association schemes of coding theory”, Philips Res. Rep. Suppl., 10 (1973), 1–97 | MR

[8] Etzion T., Schwarz M., “Perfect constant-weight codes”, IEEE Trans. Inform. Theory, 50:9 (2004), 2156–2165 | DOI | MR

[9] Fon-der-Flaass D., “A bound on correlation immunity”, Sib. elektron. mat. izv., 2007, no. 4, 133–135 | MR | Zbl

[10] Godsil C., Royle G., Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verl., New York–Heidelberg–Berlin, 2001, 439 pp. | MR | Zbl

[11] Hanani H., “On quadruple systems”, Can. J. Math., 12 (1960), 145–157 | MR | Zbl

[12] Hartman A., Phelps K. T., “Tetrahedral quadruple systems”, Utilitas Math., 37 (1990), 181–189 | MR

[13] Martin W. J., “Completely regular designs of strength one”, J. Algebr. Comb., 3 (1994), 17–185 | DOI | MR

[14] Martin W. J., “Completely regular designs”, J. Comb. Des., 6:4 (1998), 261–273 | 3.0.CO;2-D class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[15] Meyerowitz A., “Cycle–balanced partitions in distance–regular graphs”, Discrete Math., 264 (2003), 149–165 | DOI | MR | Zbl

[16] Mogilnykh I. Yu., Avgustinovich S. V., “Perfect colorings of Johnson graph in two colors”, Proc. XI Int. Symp. Problems of Redundancy in Information and Control Systems (Saint-Petersburg, Russia, July 2–6, 2007), GUAP, Saint-Petersburg, 2007, 205–209

[17] Mogilnykh I. Yu., Avgustinovich S. V., “Perfect 2-colorings of Johnson graphs $J(6,3)$ and $J(7,3)$”, Lect. Notes Comp. Sci., 5228, 2008, 11–19 | Zbl

[18] Phelps K. T., Stinson D. R., Vanstone S. A., “The existence of simple $S_3(3,4,v)$”, Discrete Math., 77 (1989), 255–258 | DOI | MR | Zbl

[19] Shapiro G. S., Slotnik D. S., “On the mathematical theory of error correcting codes”, IBM J. Res. Dev., 3 (1959), 68–72 | DOI | MR