Том 17, номер 2, 2010 г., Стр. 3-19

УДК 621.391.15
Августинович С. В., Могильных И. Ю.
Совершенные раскраски графов Джонсона J(8, 3) и J(8, 4) в два цвета

Аннотация:
В статье перечисляются матрицы параметров всех совершенных 2-раскрасок графов Джонсона J(8, 3) и J(8, 4), приводится несколько конструкций совершенных 2-раскрасок графов Джонсона J(2w, w), J(2m, 3). Понятие совершенной раскраски является обобщением понятия полностью регулярного кода, введённого Дельсартом. Проблема существования подобных структур в графах Джонсона тесно связана с проблемой существования полностью регулярных кодов в графах Джонсона и, в частности, с гипотезой Дельсарта о несуществовании нетривиальных совершенных кодов в графах Джонсона, с проблемой существования блок-схем и другими известными проблемами. Библиогр. 19.

Ключевые слова: совершенная раскраска, схема Джонсона, блок-схема.

Августинович Сергей Владимирович ¹
Могильных Иван Юрьевич ²
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: avgust@math.nsc.ru, ivmog84@gmail.com

Статья поступила 10 августа 2009 г.