Граф Клебша

Граф Клебша
Вершин	16
Ребер	40
Радіус	2
Діаметр	2
Обхват	4
Автоморфізм	1920
Хроматичне число	4
Число черг	3
Властивості	сильно регулярний гамільтонів граф граф без трикутників граф Келі вершинно-транзитивний реберно-транзитивний дистанційно-транзитивний

У теорії графів граф Клебша — один з двох взаємодоповняльних графів, що мають 16 вершин. Один з них має 40 ребер і є 5-регулярним графом, інший має 80 ребер і є 10-регулярним графом. 80-реберний варіант — це половинний граф куба 5-го порядку. 1968 року Зайдель назвав його графом Клебша, зважаючи на його зв'язок із конфігурацією прямих поверхні четвертого порядку, яку відкрив 1868 року німецький математик Альфред Клебш. 40-реберний варіант — це складений граф куба 5 порядку. Він відомий також під назвою граф Грінвуда — Глізона після роботи Грінвуда і Глізона, в якій вони використали цей граф для обчислення числа Рамсея R(3,3,3) = 17.

Побудова

Складаний граф куба 5-го порядку (5-регулярний граф Клебша) можна побудувати, додавши ребра між протилежними вершинами графа 4-вимірного гіперкуба (В n-вимірному гіперкубі пара вершин протилежна, якщо найкоротша відстань між ними містить n ребер). Його можна побудувати також із графа 5-вимірного гіперкуба стягуванням кожної пари протилежних вершин.

Ще одна побудова, що дає той самий граф, полягає у створенні вершини для кожного елемента скінченного поля GF (16) і з'єднанні двох вершин ребром, якщо різниця відповідних елементів поля є кубом.

Половинний граф куба 5-го порядку (10-регулярний граф Клебша) — це доповнення 5-регулярного графа. Його можна також побудувати з вершин 5-вимірного гіперкуба, з'єднавши пари вершин, між якими відстань Геммінга дорівнює рівно два. Ця побудова утворює дві підмножини по 16 вершин у кожній, не пов'язаних між собою. Обидва отриманих графи ізоморфні 10-регулярному графу Клебша.

Властивості

5-регулярний граф Клебша є сильно регулярним графом 5-го степеня з параметрами $(v,k,\lambda ,\mu )=(16,5,0,2)$. Його доповнення, 10-регулярний граф Клебша, теж сильно регулярний.

5-регулярний граф Клебша є гамільтоновим, непланарним і не ейлеровим. Обидва графи є 5-вершинно зв'язними і 5-реберно-зв'язними. Підграф, породжений десятьма вершинами, які не є сусідами будь-якої вершини в цьому графі, ізоморфний графу Петерсена.

Ребра повного графа K₁₆ можна розділити на три незв'язних копії 5-регулярного графа Клебша. Оскільки граф Клебша не містить трикутників, це показує, що існує триколірне розфарбування без трикутників ребер графа K₁₆. Таким чином, число Рамсея R(3,3,3), що описує найменше число вершин у повному графі за триколірного розфарбовування без трикутників, не може бути меншим від 17. Грінвуд і Глізон використали цю побудову як частину свого доведення рівності R(3,3,3) = 17.

5-регулярний граф Клебша є графом Келлера розмірності два, і входить до сімейства графів, використовуваних для пошуку покриття евклідових просторів великої розмірності гіперкубами, що не мають спільних граней.

Алгебричні властивості

Характеристичний многочлен 5-регулярного графа Клебша — це $(x+3)^{5}(x-1)^{10}(x-5)$. Отже, граф Клебша є цілим графом — його спектр складається тільки з цілих чисел. Граф Клебша — єдиний граф із таким характеристичним многочленом.

5-регулярний граф Клебша є графом Келі з групою автоморфізмів порядку 1920, ізоморфною групі Коксетера $D_{5}$. Як у будь-якому графі Келі, група автоморфізмів діє на його вершини транзитивно, роблячи його вершинно-транзитивним. Фактично він є симетричним графом, а тому він реберно-транзитивний і дистанційно-транзитивний.

Галерея

• 
  Граф Клебша є гамільтоновим.
• 
  Ахроматичне число графа Клебша дорівнює 8.
• 
  Хроматичне число графа Клебша дорівнює 4.
• 
  Хроматичний клас графа Клебша дорівнює 5.
• 
  Побудова графа Клебша з графа гіперкуба.