Граф Деджтера

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

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

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

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