Граф Вагнера

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

Граф Вагнера
Граф Вагнера
Названо на честь
(Вершин)	8
(Ребер)	12
(Радіус)	2
(Діаметр)	2
(Обхват)	4
(Автоморфізм)	16 (D8)
Хроматичне число	3
Хроматичний індекс	3
(Рід)	1
Властивості	кубічний гамільтонів без трикутників вершинно-транзитивний тороїдальний верхівковий
Позначення	M8

Властивості

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

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

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

Характеристичний многочлен графу Вагнера дорівнює ${\displaystyle (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]⁸. Він є примірником ^[en], різновидом циркулянтного графа, у якому вершини утворюють цикл, і кожна вершина з’єднана з іншими вершинами, чиї позиції відрізняються на число, що дорівнює 1 (mod 3). Він також ізоморфний коловій кліці K_8/3.

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

Галерея

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

Примітки

1. J.A. Bondy, U.S.R. Murty. Graph Theory. — Springer, 2007. — С. 275–276. — .
2. Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. — 1999. — 1 липня.
3. Soifer Alexander. The Mathematical Coloring Book. — Springer-Verlag, 2008. — С. 245. — .
4. K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. — 1937. — Т. 114, вип. 1 (1 липня). — С. 570–590. — DOI:10.1007/BF01594196.
5. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2 (1 липня). — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4..
6. Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вип. 2 (1 липня). — С. 167–194. — DOI:10.1006/jagm.1999.1011..