Граф Вагнера — це 3-регулярний граф з 8 вершинами і 12 ребрами, є 8-вершинною драбиною Мебіуса.
Властивості Як і всі драбини Мебіуса, граф Вагнера не є планарним, але його число схрещень дорівнює одиниці, що робить його верхівковим. Граф можна вкласти без самоперетинів на тор або проєктивну площину, так що він є тороїдальним. Його обхват дорівнює 4, діаметр — 2, радіус — 2, хроматичне число — 3, хроматичний індекс — 3. Граф як вершинно 3-зв'язний, так і реберно 3-зв'язний.
Граф Вагнера має 392 кістякових дерева. Цей граф і повний граф K3,3 мають найбільше число кістякових дерев серед усіх кубічних графів з таким самим числом вершин.
Граф Вагнера є вершинно-транзитивним, але не реберно-транзитивним. Його повна група автоморфізмів ізоморфна діедричній групі D8 16-го порядку, групі симетрій восьмикутника, включаючи як обертання, так і відображення.
Характеристичний многочлен графу Вагнера дорівнює . Це єдиний граф, який має такий многочлен, як наслідок, граф визначається однозначно за спектром.
Граф Вагнера не містить трикутників і його незалежна множина вершин дорівнює трьом, що дає половину доведення, що число Рамсея R(3,4) (найменше число n, таке що будь-який граф з n вершинами містить або трикутник, або незалежну множину з чотирьох вершин) дорівнює 9.
Мінори графу Драбини Мебіуса відіграють важливу роль у теорії мінорів графу. Найранішим результатом такого типу є теорема 1937 року Клауса Вагнера (частина групи результатів, відомих як теорема Вагнера), про те що графи, які не містять мінорів K5, можна утворити за допомогою сум за кліками планарних графів і драбини Мебіуса M8. З цієї причини M8 називають графом Вагнера.
Граф Вагнера є одним з чотирьох мінімальних заборонених мінорів для графів з деревною шириною, що не перевищує трьох, (інші три — це повний граф K5, граф правильного октаедра і граф п'ятикутної призми) і одним з чотирьох мінімальних заборонених мінорів для графів з шириною гілок максимум три (інші три — це K5, граф октаедра і граф куба...
Побудова Граф Вагнера є кубічним і гамільтоновим і має LCF-позначення 8. Він є примірником , різновидом циркулянтного графа, у якому вершини утворюють цикл, і кожна вершина з’єднана з іншими вершинами, чиї позиції відрізняються на число, що дорівнює 1 (mod 3). Він також ізоморфний коловій кліці .
Граф можна побудувати як драбину з чотирма щаблями на циклі топологічної стрічки Мебіуса.
Галерея
Примітки