График Вагнера

График Вагнера
График Вагнера
Названный в честь	Клаус Вагнер
Вершины	8
Края	12
Радиус	2
Диаметр	2
Обхват	4
Автоморфизмы	16 ( пр. ₈ )
Хроматическое число	3
Хроматический индекс	3
Род	1
Характеристики	Кубический гамильтониан без треугольников вершинно-транзитивный тороидальный апекс
Обозначение	M ₈
Таблица графиков и параметров

В математической области теории графов , то граф Вагнера представляет собой 3- регулярный граф с 8 вершинами и 12 ребрами. ^[1] Это лестничный граф Мебиуса с 8 вершинами .

Свойства [ править ]

Как лестница Мёбиуса, граф Вагнера неплоский, но имеет пересечение номер один, что делает его вершинным графом . Его можно вложить без пересечений в тор или проективную плоскость , поэтому он также является тороидальным графом . Он имеет обхват 4, диаметр 2, радиус 2, хроматическое число 3, хроматический индекс 3 и является как 3- вершинно-связанным, так и 3 -реберным .

Граф Вагнера имеет 392 остовных дерева ; он и полный граф K _3,3 имеют самые остовные деревья среди всех кубических графов с одинаковым числом вершин. ^[2]

Граф Вагнера является вершинно-транзитивным графом, но не является реберно-транзитивным . Его полная группа автоморфизмов изоморфна группе диэдра D ₈ порядка 16, группе симметрий восьмиугольника , включая как вращения, так и отражения.

Характеристический полином графа Вагнер . Это единственный граф с таким характеристическим многочленом, что делает его графом, определяемым его спектром. ${\ Displaystyle (х-3) (х-1) ^ {2} (х + 1) (х ^ {2} + 2x-1) ^ {2}}$

Граф Вагнера не содержит треугольников и имеет независимость номер три, обеспечивая половину доказательства того, что число Рамсея R (3,4) (наименьшее число n такое, что любой граф с n- вершинами содержит либо треугольник, либо четырехвершинник независимое множество) равно 9. ^[3]

График миноры [ править ]

Лестницы Мебиуса играют важную роль в теории миноров графов . Самым ранним результатом этого типа является теорема Клауса Вагнера 1937 года (часть группы результатов, известная как теорема Вагнера ) о том, что графы без минора K ₅ могут быть сформированы с помощью операций кликовой суммы для объединения плоских графов и лестницы Мёбиуса M ₈ . ^[4] По этой причине M ₈ называется графом Вагнера.

Граф Вагнера также является одним из четырех минимальных запрещенных миноров для графов шириной не более трех (остальные три являются полным графом K ₅ , графиком правильного октаэдра и графиком пятиугольной призмы ) и одним из четырех минимальных запрещенных миноров для графов с шириной ветвления не более трех (остальные три - это K ₅ , граф октаэдра и граф куба ). ^[5]^[6]

Строительство [ править ]

Граф Вагнера является кубическим гамильтоновым графом и может быть определен с помощью обозначения LCF [4] ⁸ . Это пример графа Андрашфаи , типа циркулянтного графа, в котором вершины могут быть расположены в цикле, и каждая вершина соединена с другими вершинами, позиции которых различаются числом, равным 1 (mod 3). Он также изоморфен круговой клике $K 8/3$ .

Его можно нарисовать как лестничный граф с 4-мя циклическими ступенями на топологической ленте Мёбиуса .

Галерея [ править ]

Хроматическим числом графа Вагнера равно 3.
Хроматической индекс графа Вагнера равен 3.
Граф Вагнера, нарисованный на ленте Мебиуса.

Ссылки [ править ]

^ Бонди, JA ; Мурти, USR (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. DOI : 10.1007 / BF01594196 . S2CID 123534907 . CS1 maint: обескураженный параметр ( ссылка )
^ Bodlaender, Hans L. (1998). «Частичный k- арборетум графов с ограниченной шириной дерева». Теоретическая информатика . 209 (1–2): 1–45. DOI : 10.1016 / S0304-3975 (97) 00228-4 . hdl : 1874/18312 . CS1 maint: discouraged parameter (link).
^ Bodlaender, Ганс Л. ; Тиликос, Димитриос М. (1999). «Графики с шириной ветвления не более трех». Журнал алгоритмов . 32 (2): 167–194. DOI : 10.1006 / jagm.1999.1011 . hdl : 1874/2734 ..

Викискладе есть медиафайлы, связанные с графом Вагнера .

[1] Бонди, JA ; Мурти, USR (2007). Теория графов . Springer. С. 275–276. ISBN 978-1-84628-969-9.CS1 maint: несколько имен: список авторов ( ссылка )

[2] Якобсон, Дмитрий; Ривин, Игорь (1999). «О некоторых экстремальных задачах теории графов». arXiv : math.CO/9907050 .

[3] Сойфер, Александр (2008). Математическая книжка-раскраска . Springer-Verlag. п. 245. ISBN 978-0-387-74640-1..

[4] Вагнер, К. (1937). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen . 114 (1): 570–590. DOI : 10.1007 / BF01594196 . S2CID 123534907 . CS1 maint: обескураженный параметр ( ссылка )

[5] Bodlaender, Hans L. (1998). «Частичный k- арборетум графов с ограниченной шириной дерева». Теоретическая информатика . 209 (1–2): 1–45. DOI : 10.1016 / S0304-3975 (97) 00228-4 . hdl : 1874/18312 . CS1 maint: discouraged parameter (link).

[6] Bodlaender, Ганс Л. ; Тиликос, Димитриос М. (1999). «Графики с шириной ветвления не более трех». Журнал алгоритмов . 32 (2): 167–194. DOI : 10.1006 / jagm.1999.1011 . hdl : 1874/2734 ..

[1]