Граф гиперкуба

Все графы гиперкубов являются двудольными — их вершины можно раскрасить только двумя цветами. Два цвета этой раскраски можно найти из построения подмножеств графов гиперкубов путём присвоения одного цвета подмножествам, имеющим чётное число элементов и другого цвета подмножествам, имеющим нечётное число элементов.

Любой гиперкуб Q_n с n > 1 имеет гамильтонов цикл, проходящий через каждую вершину ровно один раз. Вдобавок, гамильтонов путь между вершинами u, v существует тогда и только тогда, когда u и v имеют различные цвета в двухцветной раскраске графа. Оба факта легко проверить по индукции по размерности гиперграфа с построением графа гиперкуба путём соединения двух меньших гиперкубов.

Вышеописанные свойства гиперкуба тесно связаны с теорией кодов Грея. Более точно, существует биективное соответствие между множеством n-битных циклических кодов Грея и множеством гамильтоновых циклов в гиперкубе Q_n.[1] Аналогичное свойство имеет место для ацикличных n-битных кодов Грея и гамильтоновых путей.

Меньше известен факт, что любое совершенное паросочетание в гиперкубе можно раширить до гамильтонова цикла.[2] Вопрос, можно ли любое паросочетание расширить до гамильтонова цикла, остаётся открытым.[3]

Граф гиперкуба Q_n (n > 1) :

• является диаграммой Хассе конечной булевой алгебры;
• является медианным графом. Любой медианный граф является изометричным подграфом гиперкуба и может быть образован путём усечения гиперкуба;
• имеет более чем 2^2n-2 совершенных паросочетаний (это другое следствие, следующее из индуктивного построения);
• является транзитивным относительно дуг и симметричным. Симметрии графов гиперкубов можно представить как знаковые перестановки, группа автоморфизмов изоморфна ${\displaystyle S_{n}\wr \mathbb {Z} _{2}}$;
• содержит все циклы длины 4, 6, …, 2ⁿ и поэтому является бипанциклическим графом;
• может быть нарисован как граф единичных расстояний на евклидовой плоскости путём выбора единичного вектора для каждого элемента множества и размещения каждой вершины, соответствующей множеству S, в точке, соответствующей сумме векторов из S;
• является вершинно n-связным графом по теореме Балинского;
• является планарным (может быть нарисован без пересечений) в том и только в том случае, когда n ≤ 3. Для больших значений n гиперкуб имеет род ${\displaystyle (n-4)2^{n-3}+1}$[4][5];

• имеет в точности ${\displaystyle 2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$ остовных дерева[5];
• семейство Q_n (n > 1) является семейством графов Леви;
• известно, что ахроматическое число графа Q_n пропорционально ${\displaystyle {\sqrt {n2^{n}}}}$, но точная константа пропорциональности неизвестна[6];

• ширина полосы графа Q_n в точности равна ${\displaystyle \sum _{i=0}^{n}{\binom {n}{\lfloor n/2\rfloor }}}$.[7];
• собственные значения матрицы инцидентности равны (-n,-n+2,-n+4,…,n-4,n-2,n), а собственные значения матрицы Кирхгофа графа равны (0,2,…,2n);
• изопериметрическое число равно h(G)=1.