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

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

Будь-який гіперкуб Q_n с n > 1 має гамільтонів цикл, що проходить через кожну вершину рівно один раз. В додаток, гамільтонів шлях між вершинами U, V існує тоді і тільки тоді, коли u и v мають різні кольори в двокольоровому розфарбуванні графа. Обидва факти легко перевірити по індукції по розмірності гіперграфа з побудовою графа гіперкуба шляхом з'єднання двох менших гіперкубів.

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

Менше відомий факт, що будь-яке зроблене паросполучення в гіперкубі можна розширити до Гамільтона циклу.[2] Питання, чи можна будь-яке паросполучення розширити до Гамільтона циклу, залишається відкритим.[3]

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

• є діаграмою Хассе кінцевої булевої алгебри;

• є медійним графом. Будь який медійний граф є ізометричним підграфом гіперкуба і може бути утворений шляхом усічення гіперкуба;

• має більш ніж 2^2n-2 зроблених паросполучень (це інший наслідок, наступне з індуктивного побудови);

• є транзитивним щодо дуг та симетричним. Симетрії графів гіперкубів можна представити як знакові перестановки;

• містить всі цикли довжини 4, 6, …, 2n і тому є біпанциклічним графом;
• може бути намальований як граф одиничних відстаней на евклідовій площині шляхом вибору одиничного вектора для кожного елемента  множини і розміщення кожної вершини, відповідно множини 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, + 4 -n, …, п-4, п-2, п), а власні значення матриці Кірхгофа графа рівні (0,2, …, 2n);

• Ізопериметричне число дорівнює h(G)=1.