| Граф Вагнера | |
|---|---|
 | |
| Назван в честь | Клауса Вагнера[en] |
| Вершин | 8 |
| Рёбер | 12 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 4 |
| Автоморфизмы | 16 (D8) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Свойства |
кубический
вершинный |
Граф Вагнера — это 3-регулярный граф с 8 вершинами и 12 рёбрами[1], является 8-вершинной лестницей Мёбиуса.
Свойства
Как и все лестницы Мёбиуса, граф Вагнера не является планарным но его число скрещиваний[en]* равно единице, что делает его вершинным[en]. Граф можно вложить без самопересечений на тор или проективную плоскость, так что он является тороидальным. Его обхват равен 4, диаметр — 2, радиус — 2, хроматическое число — 3, хроматический индекс — 3. Граф как вершинно 3-связный так и рёберно 3-связный.
Граф Вагнера имеет 392 остовных дерева. Этот граф и полный граф K3,3 имеют наибольшее число остовных деревьев среди всех кубических графов с таким же числом вершин[2].
Граф Вагнера является вершинно-транзитивным, но не рёберно-транзитивным. Его полная группа автоморфизмов изоморфна диэдрической группе D8 16-го порядка, группе симметрий восьмиугольника, включая как вращения, так и отражения.
Характеристический многочлен графа Вагнера равен . Это единственный граф, имеющий такой многочлен, в результате чего граф определяется однозначно по спектру.
Граф Вагнера не содержит треугольников и его независимое множество вершин равно трём, что даёт половину доказательства, что число Рамсея R(3,4) (наименьшее число n, такое что любой граф с n вершинами содержит либо треугольник, либо независимое множество из четырёх вершин) равно 9[3].
Миноры графа
Лестницы Мёбиуса играют важную роль в теории миноров графа. Самым ранним результатом такого типа является теорема 1937 года Клауса Вагнера[en] (часть группы результатов, известных как Теорема Вагнера), о том что графы, не содержащие миноров K5, могут быть образованы с помощью сумм по кликам планарных графов и лестницы Мёбиуса M8[4]. По этой причине M8 называют графом Вагнера.
Граф Вагнера является одним из четырёх минимальных запрещённых миноров[en] для графов с древесной шириной, не превосходящей трёх, (остальные три — это полный граф K5, граф правильного октаэдра и граф пятиугольной призмы) и одним из четырёх минимальных запрещённых миноров для графов с шириной веток[en] максимум три (остальные три — это K5, граф октаэдра и граф куба[5][6].
Построение
Граф Вагнера является кубическим и гамильтоновым и имеет LCF-обозначение [4]8.
Граф можно построить как лестницу[en] с четырьмя перекладинами на цикле топологической ленты Мёбиуса.
Галерея
Хроматическое число графа Вагнера равно 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..
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .