Граф Деджтера — это 6-регулярный граф с 112 вершинами, 336 рёбрами и обхватом 4. Граф Деджтера получается путём удаления копии кода Хэмминга длины 7 из бинарного 7-куба.

Описание Граф Деджтера и любой граф, полученный удалением кода Хэмминга длины 2r-1 из (2r-1)-куба, является симметричным графом (а потому вершинно-транзитивным и рёберно-транзитивным, но не полутранзитивным). В частности, граф Деджтера допускает 3-разложение на две копии графа Любляны, который является третьим по счёту наименьшим рёберно-транзитивным графом, но не вершинно-транзитивным графом регулярной степени 3. Такие графы называются полусимметричными кубическими графами.

Фактически, доказано, что граф Деджтера может быть раскрашен в 2 цвета (например красный и синий), как на верхней фигуре справа, так что оба графа, состоящие из рёбер одного цвета, являются копиями графа Любляны. Эти две копии содержат 112 вершин графа Деджтера и 168 рёбер в каждом, обе копии имеют обхват 10, в то время как граф Деджтера имеет обхват 6, а 7-куб имеет обхват 4. По-видимому, граф Деджтера является наименьшим симметричным графом, имеющим связный самодополнительный стягивающий вершины полусимметричный кубический подграф.

Оба, красный и синий подграфы Любляны, соединяющие вершины графа Деджтера, могут быть представлены как накрывающие графы графа Хивуда, а именно 8-покрытия графа Хивуда. Это можно получить в каждом из двух представлений графа Любляны (красный сверху, синий снизу, оба справа) путём поочерёдной раскраски последовательных вершин графа Хивуда, скажем, в чёрный и белый (лучше видно при двойном клике на изображение для увеличения размера), поскольку граф Хивуда двудолен. Каждое такое изображение формируется 8 соседями вдоль фиксированной координаты 7-куба, половины кода Хэмминга, имеющего фиксированные веса 0 или 1. При обмене этих весов путём перестановки (0 и 1) можно перейти от смежности, определённой красным графом Любляны, к смежности, определённой синим графом Любляны и наоборот.

Седьмая часть графа Деджтера показана на отдельном рисунке и она может быть получена из двух получающихся копий графа Хивуда.

Примечания

Литература

Категория:Графы, имеющие собственные названия Категория:Регулярные графы