Граф Вагнера

Кубический граф с 8 вершинами и 12 ребрами

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

Характеристики

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

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

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

Характеристический полином графа Вагнера равен

${\displaystyle (x-3)(x-1)^{2}(x+1)(x^{2}+2x-1)^{2}.}$

Это единственный граф с этим характеристическим полиномом, что делает его графом, определяемым его спектром .

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

Миноры графа

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

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

Строительство

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

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

Галерея

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

Рекомендации

1. Бонди, Дж.А .; Мурти, USR (2007). Теория графов . Спрингер. стр. 275–276. ISBN 978-1-84628-969-9.
2. Якобсон, Дмитрий; Ривин, Игорь (1999). «О некоторых экстремальных задачах теории графов». arXiv : math.CO/9907050 .
3. Сойфер, Александр (2008). Математическая раскраска . Спрингер-Верлаг. п. 245. ИСБН 978-0-387-74640-1.
4. Вагнер, К. (1937). «Über eine Eigenschaft der ebenen Komplexe». Mathematische Annalen (на немецком языке). 114 (1): 570–590. дои : 10.1007/BF01594196. S2CID  123534907.
5. Бодлендер, Ханс Л. (1998). «Частичный k -дендрарий графов с ограниченной шириной дерева». Теоретическая информатика . 209 (1–2): 1–45. дои : 10.1016/S0304-3975(97)00228-4. hdl : 1874/18312 .
6. Бодлендер, Ганс Л .; Тиликос, Димитриос М. (1999). «Графы с шириной ветвей не более трех». Журнал алгоритмов . 32 (2): 167–194. дои : 10.1006/jagm.1999.1011. hdl : 1874/2734 .