Граф Вагнера

Шаблон:Граф Граф Вагнера — це 3-регулярний граф з 8 вершинами і 12 ребрами, є 8-вершинною драбиною Мебіуса.

Властивості

Як і всі драбини Мебіуса, граф Вагнера не є планарним, але його число схрещень дорівнює одиниці, що робить його верхівковим. Граф можна вкласти без самоперетинів на тор або проєктивну площину, так що він є тороїдальним. Його обхват дорівнює 4, діаметр — 2, радіус — 2, хроматичне число — 3, хроматичний індекс — 3. Граф як вершинно 3-зв'язний, так і реберно 3-зв'язний.

Граф Вагнера має 392 кістякових дерева. Цей граф і повний граф K_3,3 мають найбільше число кістякових дерев серед усіх кубічних графів з таким самим числом вершин.

Граф Вагнера є вершинно-транзитивним, але не реберно-транзитивним. Його повна група автоморфізмів ізоморфна діедричній групі D₈ 16-го порядку, групі симетрій восьмикутника, включаючи як обертання, так і відображення.

Характеристичний многочлен графу Вагнера дорівнює $(x-3)(x-1{)}^2(x+1)(x^2+2x-1{)}^2$. Це єдиний граф, який має такий многочлен, як наслідок, граф визначається однозначно за спектром.

Граф Вагнера не містить трикутників і його незалежна множина вершин дорівнює трьом, що дає половину доведення, що число Рамсея R(3,4) (найменше число n, таке що будь-який граф з n вершинами містить або трикутник, або незалежну множину з чотирьох вершин) дорівнює 9.

Мінори графу

Драбини Мебіуса відіграють важливу роль у теорії мінорів графу. Найранішим результатом такого типу є теорема 1937 року Клауса Вагнера (частина групи результатів, відомих як теорема Вагнера), про те що графи, які не містять мінорів K_5, можна утворити за допомогою сум за кліками планарних графів і драбини Мебіуса M₈. З цієї причини M₈ називають графом Вагнера.

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

Побудова

Граф Вагнера є кубічним і гамільтоновим і має LCF-позначення [4]⁸. Він є примірником Шаблон:Нп, різновидом циркулянтного графа, у якому вершини утворюють цикл, і кожна вершина з’єднана з іншими вершинами, чиї позиції відрізняються на число, що дорівнює 1 (mod 3). Він також ізоморфний коловій кліці Шаблон:Math.

Граф можна побудувати як драбину з чотирма щаблями на циклі топологічної стрічки Мебіуса.

Галерея

• 
  Хроматичне число графу Вагнера дорівнює 3.
• 
  Хроматичний індекс графу Вагнера дорівнює 3.
• 
  Граф Вагнера у вигляді стрічки Мебіуса.