График Вагнера - Wagner graph
| График Вагнера | |
|---|---|
 График Вагнера | |
| Названный в честь | Клаус Вагнер |
| Вершины | 8 |
| Края | 12 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 4 |
| Автоморфизмы | 16 (D8) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Род | 1 |
| Характеристики | Кубический Гамильтониан Без треугольников Вершинно-транзитивный Тороидальный Апекс |
| Обозначение | M8 |
| Таблица графиков и параметров | |
в математический поле теория графов, то График Вагнера это 3-регулярный график с 8 вершинами и 12 ребрами.[1] Это 8-вершина Лестница Мебиуса график.
Характеристики
Как лестница Мёбиуса, граф Вагнера непланарный но имеет номер перехода один, что делает его вершина графика. Его можно врезать без пересечений на тор или же проективная плоскость, так что это также тороидальный граф. Имеет обхват 4, диаметр 2, радиус 2, хроматическое число 3, хроматический индекс 3 и одновременно 3-вершинно-связанный и 3-реберный.
График Вагнера насчитывает 392 остовные деревья; это и полный график K3,3 имеют самые остовные деревья среди всех кубических графов с одинаковым числом вершин.[2]
Граф Вагнера - это вершинно-транзитивный граф но не ребро-транзитивный. Его полная группа автоморфизмов изоморфна группе группа диэдра D8 порядка 16 группа симметрий восьмиугольник, включая как вращения, так и отражения.
В характеристический многочлен графа Вагнера . Это единственный граф с таким характеристическим полиномом, что делает его графом, определяемым его спектром.
График Вагнера без треугольников и имеет число независимости три, обеспечивая половину доказательства того, что Число Рамсея р(3,4) (наименьшее число п такой, что любой п-вершинный граф содержит либо треугольник, либо независимое множество с четырьмя вершинами) равно 9.[3]
График миноров
Лестницы Мебиуса играют важную роль в теории граф миноры. Самый ранний результат этого типа - теорема 1937 г. Клаус Вагнер (часть группы результатов, известной как Теорема Вагнера ), что графы без K5 минор может быть сформирован с помощью кликовая сумма операции объединения плоских графов и лестницы Мёбиуса M8.[4] По этой причине M8 называется графом Вагнера.
Граф Вагнера также является одним из четырех минимальных запрещенные несовершеннолетние для графиков ширина дерева не более трех (остальные три являются полный график K5, график правильный октаэдр, а график пятиугольная призма ) и один из четырех минимальных запрещенных миноров для графов ширина ответвления не более трех (остальные три K5, график октаэдра и куб граф ).[5][6]
Строительство
Граф Вагнера - это кубический Гамильтонов граф и может быть определена Обозначение LCF [4]8. Это пример Андрашфаи граф, тип циркулянтный график в котором вершины могут быть расположены в цикл, и каждая вершина соединена с другими вершинами, чьи позиции отличаются на число, равное 1 (mod 3). Он также изоморфен круговая клика K8/3.
Его можно нарисовать как лестничный график с 4-мя ступенями, сделанными циклически на топологической Лента Мебиуса.
Галерея
В хроматическое число графа Вагнера равно 3.
В хроматический индекс графа Вагнера равно 3.
Граф Вагнера, нарисованный на ленте Мебиуса.
Рекомендации
- ^ Бонди, Дж. А.; Мурти, США. (2007). Теория графов. Springer. С. 275–276. ISBN 978-1-84628-969-9.CS1 maint: несколько имен: список авторов (связь)
- ^ Якобсон, Дмитрий; Ривин, Игорь (1999). «О некоторых экстремальных задачах теории графов». arXiv:math.CO/9907050.
- ^ Сойфер, Александр (2008). Математическая книжка-раскраска. Springer-Verlag. п. 245. ISBN 978-0-387-74640-1..
- ^ Вагнер, К. (1937). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen. 114 (1): 570–590. Дои:10.1007 / BF01594196. S2CID 123534907.
- ^ Бодландер, Ханс Л. (1998). "Частичный k-арборетум графов с ограниченной шириной дерева ». Теоретическая информатика. 209 (1–2): 1–45. Дои:10.1016 / S0304-3975 (97) 00228-4. HDL:1874/18312..
- ^ Бодландер, Ханс Л.; Тиликос, Димитриос М. (1999). «Графы с шириной ветвления не более трех». Журнал алгоритмов. 32 (2): 167–194. Дои:10.1006 / jagm.1999.1011. HDL:1874/2734..