Граф Вагнера
Граф Вагнера — це 3-регулярний граф з 8 вершинами і 12 ребрами[1], є 8-вершинною драбиною Мебіуса.
| Граф Вагнера | |
|---|---|
 Граф Вагнера | |
| Названо на честь | Клаус Вагнер |
| Вершин | 8 |
| Ребер | 12 |
| Радіус | 2 |
| Діаметр | 2 |
| Обхват | 4 |
| Автоморфізм | 16 (D8) |
| Хроматичне число | 3 |
| Хроматичний індекс | 3 |
| Рід | 1 |
| Властивості |
кубічний гамільтонів без трикутників вершинно-транзитивний тороїдальний верхівковий |
| Позначення | M8 |
Властивості ред.
Як і всі драбини Мебіуса, граф Вагнера не є планарним, але його число схрещень дорівнює одиниці, що робить його верхівковим. Граф можна вкласти без самоперетинів на тор або проєктивну площину, так що він є тороїдальним. Його обхват дорівнює 4, діаметр — 2, радіус — 2, хроматичне число — 3, хроматичний індекс — 3. Граф як вершинно 3-зв'язний, так і реберно 3-зв'язний.
Граф Вагнера має 392 кістякових дерева. Цей граф і повний граф K3,3 мають найбільше число кістякових дерев серед усіх кубічних графів з таким самим числом вершин[2].
Граф Вагнера є вершинно-транзитивним, але не реберно-транзитивним. Його повна група автоморфізмів ізоморфна діедричній групі D8 16-го порядку, групі симетрій восьмикутника, включаючи як обертання, так і відображення.
Характеристичний многочлен графу Вагнера дорівнює . Це єдиний граф, який має такий многочлен, як наслідок, граф визначається однозначно за спектром.
Граф Вагнера не містить трикутників і його незалежна множина вершин дорівнює трьом, що дає половину доведення, що число Рамсея R(3,4) (найменше число n, таке що будь-який граф з n вершинами містить або трикутник, або незалежну множину з чотирьох вершин) дорівнює 9[3].
Мінори графу ред.
Драбини Мебіуса відіграють важливу роль у теорії мінорів графу. Найранішим результатом такого типу є теорема 1937 року Клауса Вагнера (частина групи результатів, відомих як теорема Вагнера), про те що графи, які не містять мінорів K5, можна утворити за допомогою сум за кліками планарних графів і драбини Мебіуса M8[4]. З цієї причини M8 називають графом Вагнера.
Граф Вагнера є одним з чотирьох мінімальних заборонених мінорів для графів з деревною шириною, що не перевищує трьох, (інші три — це повний граф K5, граф правильного октаедра і граф п'ятикутної призми) і одним з чотирьох мінімальних заборонених мінорів для графів з шириною гілок максимум три (інші три — це K5, граф октаедра і граф куба[5][6].
Побудова ред.
Граф Вагнера є кубічним і гамільтоновим і має LCF-позначення [4]8. Він є примірником графа Андрашфаї[en], різновидом циркулянтного графа, у якому вершини утворюють цикл, і кожна вершина з’єднана з іншими вершинами, чиї позиції відрізняються на число, що дорівнює 1 (mod 3). Він також ізоморфний коловій кліці K8/3.
Граф можна побудувати як драбину з чотирма щаблями на циклі топологічної стрічки Мебіуса.
Галерея ред.
-
Хроматичне число графу Вагнера дорівнює 3. -
Хроматичний індекс графу Вагнера дорівнює 3. -
Граф Вагнера у вигляді стрічки Мебіуса.
Примітки ред.
- ↑ J.A. Bondy, U.S.R. Murty. Graph Theory. — Springer, 2007. — С. 275–276. — ISBN 978-1-84628-969-9.
- ↑ Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. — 1999. — 24 квітня.
- ↑ Soifer Alexander. The Mathematical Coloring Book. — Springer-Verlag, 2008. — С. 245. — ISBN 978-0-387-74640-1.
- ↑ K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. — 1937. — Т. 114, вип. 1 (24 квітня). — С. 570–590. — DOI:.
- ↑ Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2 (24 квітня). — С. 1–45. — DOI:..
- ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вип. 2 (24 квітня). — С. 167–194. — DOI:..