Граф Вагнера
| Граф Вагнера | |
|---|---|
 | |
| Назван в честь | Клауса Вагнера |
| Вершин | 8 |
| Рёбер | 12 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 4 |
| Автоморфизмы | 16 (D8) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Свойства |
кубический
вершинный |
Граф Вагнера — это 3-регулярный граф с 8 вершинами и 12 рёбрами[1], является 8-вершинной лестницей Мёбиуса.
Свойства
Как и все лестницы Мёбиуса, граф Вагнера не является планарным, но его число скрещиваний равно единице, что делает его верхушечным. Граф можно вложить без самопересечений на тор или проективную плоскость, так что он является тороидальным. Его обхват равен 4, диаметр — 2, радиус — 2, хроматическое число — 3, хроматический индекс — 3. Граф как вершинно 3-связный так и рёберно 3-связный.
Граф Вагнера имеет 392 остовных дерева. Этот граф и полный граф K3,3 имеют наибольшее число остовных деревьев среди всех кубических графов с таким же числом вершин[2].
Граф Вагнера является вершинно-транзитивным, но не рёберно-транзитивным. Его полная группа автоморфизмов изоморфна диэдрической группе D8 16-го порядка, группе симметрий восьмиугольника, включая как вращения, так и отражения.
Характеристический многочлен графа Вагнера равен [math]\displaystyle{ (x-3)(x-1)^2(x+1)(x^2+2x-1)^2 }[/math]. Это единственный граф, имеющий такой многочлен, в результате чего граф определяется однозначно по спектру.
Граф Вагнера не содержит треугольников и его независимое множество вершин равно трём, что даёт половину доказательства, что число Рамсея R(3,4) (наименьшее число n, такое что любой граф с n вершинами содержит либо треугольник, либо независимое множество из четырёх вершин) равно 9[3].
Миноры графа
Лестницы Мёбиуса играют важную роль в теории миноров графа. Самым ранним результатом такого типа является теорема 1937 года Клауса Вагнера (часть группы результатов, известных как теорема Вагнера), о том что графы, не содержащие миноров K5, могут быть образованы с помощью сумм по кликам планарных графов и лестницы Мёбиуса M8[4]. По этой причине M8 называют графом Вагнера.
Граф Вагнера является одним из четырёх минимальных запрещённых миноров для графов с древесной шириной, не превосходящей трёх, (остальные три — это полный граф K5, граф правильного октаэдра и граф пятиугольной призмы) и одним из четырёх минимальных запрещённых миноров для графов с шириной веток максимум три (остальные три — это K5, граф октаэдра и граф куба[5][6].
Построение
Граф Вагнера является кубическим и гамильтоновым и имеет LCF-обозначение [4]8.
Граф можно построить как лестницу с четырьмя перекладинами на цикле топологической ленты Мёбиуса.
Галерея
-
Хроматическое число графа Вагнера равно 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.
- ↑ 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. — С. 570–590. — doi:10.1007/BF01594196.
- ↑ Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вып. 1–2. — С. 1–45. — doi:10.1016/S0304-3975(97)00228-4..
- ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вып. 2. — С. 167–194. — doi:10.1006/jagm.1999.1011..