Совершенные 2-раскраски графов Джонсона

• Автор: Могильных, Иван Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 105 с.

Оглавление
Введение
1 Конструкции совершенных 2-раскрасок графов Джонсона
2 Необходимые условия существования совершенных 2-раскрасок графов Джонсона
2.1 Спектр белых вершин совершенной 2-раскраски относительно дистанционно-регулярного расслоения
2.2 Пространства собственных векторов и свойство к-регулярности совершенных раскрасок
2.2.1 Собственные значения и собственные векторы графов
2.2.2 Собственные значения совершенных 2-раскрасок графа Джонсона и свойство к-регулярности
2.3 Нижняя оценка параметра «21 совершенной 2-раскраски графа Джонсона
2.4 Несуществование некоторых совершенных 2-раскрасок графов Джонсона
3 Совершенные 2-раскраски графов Л(п^), п < 8
3.1 Совершенные 2-раскраски графа 4(6,3)
3.2 Совершенные 2-раскраски графа 4(7.3)
3.3 Совершенные 2-раскраски графа 7(8,3)
3.4 Совершенные 2-раскраски графа 4(8,4)
4 Слабые изометрии кодов Препараты

4.1 Слабые изометрии выколотых кодов Препараты
4.2 Слабые изометрии кодов Препараты
5 Приложение
Литература

Введение
В данной диссертации исследуется вопрос существования совершенных 2-раскрасок графов Джонсона. Под совершенной раскраской в т цветов (совершенной т-раскраской) графа С с матрицей Л = {ау}гд=1 понимается раскраска множества вершин графа С в множество цветов {1,..., т.} такая, что число вершин цвета у, смежных с фиксированной вершиной цвета г, не зависит от выбора последней вершины и равно ау. Матрица А называется матрицей параметров совершенной раскраски. В случае т = 2, цвет под номером 1 будем называть белым, а цвет под номером 2 - черным; совокупность всех вершин белого цвета графа С? будем обозначать ¥, черного - В. В случае двуцветной совершенной раскраски, параметр аи будем называть внутренней степенью і-го цвета, а параметр ау ффі будем называть внешней степенью і-го цвета.
Обозначим через Еп совокупность всех двоичных векторов длины п. Расстоянием Хэмминга между двумя векторами х и у из Еп называют количество различных координат в векторах х и у. Граф Джонсона Лп,из) (названный в честь первого из исследователей одноименной схе--мы ассоциативности [39]) определяется как граф, вершинами которого являются всевозможные вектора из Еп веса го, пара векторов соединяется ребром, если они находятся на расстоянии 2 по Хэммингу. Наименьшее число ребер графа Джонсона в пути, соединяющем вершины ж и у называется расстояниелі Джонсона. Отметим, что граф Лп,иі) является изоморфным графу 7(тг,п — го). Поэтому в настоящей диссертации

Эта матрица порядка 3 обладает следующим интересным свойством: в каждом столбце два внедиагональиых элемента равны, что позволяет с помощью Леммы 2 объединять соответствующие цвета. Например, покрасим белым цветом вершины первого или второго цвета, а третьего - черным цветом. Тогда любая вершина белого цвета видит одинаковое количество вершин белого цвета в силу указанного свойства матриц, и матрица параметров полученной совершенной раскраски в два цвета
первый и третий цвета, получим совершенные раскраски с матрицами параметров
соответственно.
Теперь приведем две конструкции совершенных 2-раскрасок графа ,/(2гг,гг). Нижеприведенные совершенные 2-раскраски были получены объединением цветов орбитной раскраски, соответствующей стабилизатору нескольких координат на множестве вершин графа Джонсона.
Конструкция 3.
Пусть х является произвольным двоичным вектором веса 2 длины 2гг. Согласно [42] шапка относительно вектора х является полностью регулярным кодом. Рассмотрим совершенную раскраску ,/(2гг, гг), индуцированную шапкой относительно х. Матрица параметров этой совершенной раскраски однозначно определяется массивом пересечений шапки относительно х и согласно Теореме 2 имеет следующий вид:
3(2т — 5)
4 (т — 2) 2 т —
Объединяя второй и третьи цвета,
3(т — 3) 3 т
т — 2 5 т —
/ 3(т — 1) 3(т — 2) (т
+ 4) Ът —
( гг(гг — 2) 2ъи
гг — 1 (гг — I)2 + 1 I 0 2гг