Граф Вагнера

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

Граф Вагнера
Граф Вагнера
Названий на честь Клаус Вагнер
Вершин 8
Ребер 12
Радіус 2
Діаметр 2
Обхват 4
Автоморфізм 16 (D8)
Хроматичне число 3
Хроматичний індекс 3
Genus 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.

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

Галерея

Примітки
  1. J.A. Bondy, U.S.R. Murty. Graph Theory. — Springer, 2007. — С. 275–276. — ISBN 978-1-84628-969-9.
  2. Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. — 1999. — 21 січня.
  3. Soifer Alexander. The Mathematical Coloring Book. — Springer-Verlag, 2008. — С. 245. — ISBN 978-0-387-74640-1.
  4. K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. — 1937. — Т. 114, вип. 1 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 167–194. — DOI:10.1006/jagm.1999.1011..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.